# 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 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: