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 allclose all

Basic Examples  (2)

Find a largest 2-plex in a graph:

Show the 2-plex:

Find all 4-plexes:

Scope  (13)

Specification  (6)

FindKPlex works with undirected graphs:

Directed graphs:

Multigraphs:

Mixed graphs:

Find k-plexes for arbitrary k:

Use rules to specify the graph:

Enumeration  (7)

Find a largest 2-plex:

A 2-plex containing exactly 2 vertices:

A 2-plex containing at most 4 vertices:

A 2-plex containing between 3 and 5 vertices:

A largest 2-plex that includes a given vertex:

Find all 2-plexes in a graph:

FindKPlex gives an empty list if there is no plex:

Applications  (2)

Highlight all 2-plexes of size 4:

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:

Properties & Relations  (5)

A 1-plex is a clique:

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

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

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

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

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

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_2023_findkplex, author="Wolfram Research", title="{FindKPlex}", year="2015", howpublished="\url{https://reference.wolfram.com/language/ref/FindKPlex.html}", note=[Accessed: 20-April-2024 ]}

BibLaTeX

@online{reference.wolfram_2023_findkplex, organization={Wolfram Research}, title={FindKPlex}, year={2015}, url={https://reference.wolfram.com/language/ref/FindKPlex.html}, note=[Accessed: 20-April-2024 ]}