What is a k-Plex? | Graph Theory

What is a k-plex in graph theory? This is another graph substructure representing cohesive social networks. We'll define k-plexes, which are a relaxation of the clique structure, in today's graph theory video lesson!

A graph G=(V,E) is a k-plex if the degree of every vertex in G has a degree of at least |V|-k. In other words, each vertex is not adjacent to at most k other vertices, so the minimum degree of the graph is at least |V|-k. We can define k-plexes as vertex subsets in a similar way.

Lesson on cliques:    • What is a Clique? | Graph Theory, Cli...  
Lesson on k-cliques:    • What are k-Cliques? | Graph Theory  
Lesson on k-cores:    • What is the K-Core of a Graph? | K-Co...  
Lesson on k-clans and k-clubs:    • What are k-Clans and k-Clubs? | Graph...  

Some references on k-plexes...
http://aris.ss.uci.edu/~lin/65.pdf
https://www.caam.rice.edu/~ivhicks/kp...

◆ Donate on PayPal: https://www.paypal.me/wrathofmath
◆ Support Wrath of Math on Patreon:   / wrathofmathlessons  

I hope you find this video helpful, and be sure to ask any questions down in the comments!

+WRATH OF MATH+

Follow Wrath of Math on...
● Instagram:   / wrathofmathedu  
● Facebook:   / wrathofmath  
● Twitter:   / wrathofmathedu  

My Music Channel:    / seanemusic