WOLFRAM

Wolfram Language & System Documentation Center

FindKPlex[g,k]

finds a largest k-plex in the graph g.

FindKPlex[g,k,n]

finds a k-plex containing at most n vertices.

FindKPlex[g,k,{n}]

finds a k-plex containing exactly n vertices.

FindKPlex[g,k,{nmin,nmax}]

finds a k-plex containing between nmin and nmax vertices.

FindKPlex[g,k,nspec,s]

finds at most s k-plexes.

FindKPlex[{g,v},k,…]

finds k-plexes that include the vertex v only.

FindKPlex[{vw,…},…]

uses rules vw to specify the graph g.

Details
Details and Options Details and Options
Examples  
Basic Examples  
Scope  
Specification  
Enumeration  
Applications  
Properties & Relations  
See Also
Related Guides
History
Cite this Page

FindKPlex

FindKPlex[g,k]

finds a largest k-plex in the graph g.

FindKPlex[g,k,n]

finds a k-plex containing at most n vertices.

FindKPlex[g,k,{n}]

finds a k-plex containing exactly n vertices.

FindKPlex[g,k,{nmin,nmax}]

finds a k-plex containing between nmin and nmax vertices.

FindKPlex[g,k,nspec,s]

finds at most s k-plexes.

FindKPlex[{g,v},k,…]

finds k-plexes that include the vertex v only.

FindKPlex[{vw,…},…]

uses rules vw to specify the graph g.

Details

  • A k-plex is a maximal set of vertices such that each vertex is adjacent to all except k others.
  • For a directed graph, the outgoing edges for each vertex connect to all except k others.
  • FindKPlex returns a list of k-plexes.
  • FindKPlex will return an empty list if there is no k-plex.
  • FindKPlex[…,k,nspec,All] finds all the k-plexes.
  • FindKPlex works with undirected graphs, directed graphs, multigraphs, and mixed graphs.

Examples

open all close all

Basic Examples  (2)

Find a largest 2-plex in a graph:

Wolfram Language code: g = [image];
Wolfram Language code: FindKPlex[g, 2]

Show the 2-plex:

Wolfram Language code: HighlightGraph[g, Subgraph[g, %], GraphHighlightStyle -> "Thick"]

Find all 4-plexes:

Wolfram Language code: g = ExampleData[{"NetworkGraph", "ZacharyKarateClub"}];
Wolfram Language code: FindKPlex[g, 4, Infinity, All]//Shallow

Scope  (13)

Specification  (6)

FindKPlex works with undirected graphs:

Wolfram Language code: FindKPlex[[image], 2]

Directed graphs:

Wolfram Language code: FindKPlex[[image], 2]

Multigraphs:

Wolfram Language code: FindKPlex[[image], 2]

Mixed graphs:

Wolfram Language code: FindKPlex[[image], 2]

Find k-plexes for arbitrary k:

Wolfram Language code: Table[FindKPlex[[image], k], {k, 1, 4}]

Use rules to specify the graph:

Wolfram Language code: FindKPlex[{1 -> 2, 1 -> 5, 2 -> 3, 3 -> 4, 4 -> 5, 3 -> 6, 4 -> 6, 6 -> 3, 6 -> 4, 4 -> 3}, 2]

Enumeration  (7)

Find a largest 2-plex:

Wolfram Language code: FindKPlex[[image], 2]

A 2-plex containing exactly 2 vertices:

Wolfram Language code: FindKPlex[[image], 2, {3}]

A 2-plex containing at most 4 vertices:

Wolfram Language code: FindKPlex[[image], 2, 4]

A 2-plex containing between 3 and 5 vertices:

Wolfram Language code: FindKPlex[[image], 2, {3, 5}]

A largest 2-plex that includes a given vertex:

Wolfram Language code: FindKPlex[{[image], 6}, 2]

Find all 2-plexes in a graph:

Wolfram Language code: FindKPlex[[image], 2, Infinity, All]

FindKPlex gives an empty list if there is no plex:

Wolfram Language code: FindKPlex[[image], 2, {5}]

Applications  (2)

Highlight all 2-plexes of size 4:

Wolfram Language code: g = GraphData[{"Antiprism", 4}];
Wolfram Language code: Table[HighlightGraph[g, Subgraph[g, i]], {i, FindKPlex[g, 2, {4}, All]}]

A network of books linked by the same buyers on Amazon.com. Find a largest selection of books including The Clinton Wars that have a common buyer to all other books within the same selection except two:

Wolfram Language code: g = ExampleData[{"NetworkGraph", "USPoliticsBooks"}];
Wolfram Language code: FindKPlex[{g, "The Clinton Wars"}, 2]

Properties & Relations  (5)

A 1-plex is a clique:

Wolfram Language code: g = [image];
Wolfram Language code: FindKPlex[g, 1]
Wolfram Language code: CompleteGraphQ[g, First[%]]

A complete graph is a maximum k-plex for arbitrary k:

Wolfram Language code: CompleteGraph[10]
Wolfram Language code: FindKPlex[%, 2]

The largest k-plex in a star graph has k+1 vertices:

Wolfram Language code: g = StarGraph[10]
Wolfram Language code: First[FindKPlex[g, 1]]
Wolfram Language code: First[FindKPlex[g, 2]]
Wolfram Language code: First[FindKPlex[g, 3]]

A (k-1)-plex is contained in a k-plex:

Wolfram Language code: g = [image];
Wolfram Language code: FindKPlex[g, 1]
Wolfram Language code: FindKPlex[g, 2, Infinity, All]

Find a largest 2-plex that includes a given vertex:

Wolfram Language code: g = [image];
Wolfram Language code: FindKPlex[{g, 6}, 2]

Compare with 2-clique, 2-clan, and 2-club:

Wolfram Language code: FindKClique[{g, 6}, 2]
Wolfram Language code: FindKClan[{g, 6}, 2]
Wolfram Language code: FindKClub[{g, 6}, 2]
Wolfram Research (2012), FindKPlex, Wolfram Language function, https://reference.wolfram.com/language/ref/FindKPlex.html (updated 2015).

Text

Wolfram Research (2012), FindKPlex, Wolfram Language function, https://reference.wolfram.com/language/ref/FindKPlex.html (updated 2015).

CMS

Wolfram Language. 2012. "FindKPlex." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2015. https://reference.wolfram.com/language/ref/FindKPlex.html.

APA

Wolfram Language. (2012). FindKPlex. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/FindKPlex.html

BibTeX

@misc{reference.wolfram_2026_findkplex, author="Wolfram Research", title="{FindKPlex}", year="2015", howpublished="\url{https://reference.wolfram.com/language/ref/FindKPlex.html}", note=[Accessed: 12-June-2026]}

BibLaTeX

@online{reference.wolfram_2026_findkplex, organization={Wolfram Research}, title={FindKPlex}, year={2015}, url={https://reference.wolfram.com/language/ref/FindKPlex.html}, note=[Accessed: 12-June-2026]}