Information System on Graph Classes and their Inclusions
Note that complements are usually not listed. So for e.g. co-fork, look for fork.
A configuration XC represents a family of graphs by specifying edges that must be present (solid lines), edges that must not be present (dotted lines), and edges that may or may not be present (not drawn). For example, XC1 represents W4, gem.
A configuration XZ represents a family of graphs by specifying edges that must be present (solid lines), edges that must not be present (not drawn), and edges that may or may not be present (red dotted lines).
Families are normally specified as XFif(n) where n implicitly starts from 0. For example, XF12n+3 is the set XF13, XF15, XF17...
XF1n (n >= 0) consists of a path P of lenth n and a vertex that is adjacent to every vertex of P. To both endpoints of P a pendant vertex is attached. Examples: XF10 = claw , XF11 = bull . XF13 = X176 .
XF2n (n >= 0) consists of a path P of length n and a vertex u that is adjacent to every vertex of P. To both endpoints of P, and to u a pendant vertex is attached. Examples: XF20 = fork , XF21 = net .
XF3n (n >= 0) consists of a path P=p1 ,..., pn+1 of length n, a triangle abc and two vertices u,v. a and c are adjacent to every vertex of P, u is adjacent to a,p1 and v is adjacent to c,pn+1. Examples: XF30 = S3 , XF31 = rising sun .
XF4n (n >= 0) consists of a path P=p1 ,..., pn+1 of length n, a P3 abc and two vertices u,v. a and c are adjacent to every vertex of P, u is adjacent to a,p1 and v is adjacent to c,pn+1. Examples: XF40 = co-antenna , XF41 = X35 .
XF5n (n >= 0) consists of a path P=p1 ,..., pn+1 of length n, and four vertices a,b,u,v. a and b are adjacent to every vertex of P, u is adjacent to a,p1 and v is adjacent to b,pn+1. Examples: XF50 = butterfly , XF51 = A . XF52 = X42 . XF53 = X47 .
XF6n (n >= 0) consists of a path P=p1 ,..., pn+1 of length n, a P2 ab and two vertices u,v. a and b are adjacent to every vertex of P, u is adjacent to a,p1 and v is adjacent to b,pn+1. Examples: XF60 = gem , XF61 = H , XF62 = X175 .
XF7n (n >= 2) consists of n independent vertices v1 ,..., vn and n-1 independent vertices w1 ,..., wn-1. wi is adjacent to vi and to vi+1. A vertex a is adjacent to all vi. A pendant edge is attached to a, v1 , vn.
XF8n (n >= 2) consists of n independent vertices v1 ,..., vn ,n-1 independent vertices w1 ,..., wn-1, and a P3 abc. wi is adjacent to vi and to vi+1. a is adjacent to v1 ,..., vn-1, c is adjacent to v2,...vn. A pendant vertex is attached to b.
XF9n (n>=2) consists of a P2n p1 ,..., p2n and a C4 abcd. pi is adjacent to a when i is odd, and to b when i is even. A pendant vertex is attached to p1 and to p2n.
XF10n (n >= 2) consists of a Pn+2 a0 ,..., an+1, a Pn+2 b0 ,..., bn+1 which are connected by edges (a1, b1) ... (an, bn).
XF11n (n >= 2) consists of a Pn+1 a0 ,..., an, a Pn+1 b0 ,..., bn and a P2 cd. The following edges are added: (a1, b1) ... (an, bn), (c, an) ... (c, bn).
are the (n+4)-pan s.
consist of an independent set U of n vertices, and an independent set W of m vertices and have an edge (v,w) whenever v in U and w in W. Example: claw , K1,4 , K3,3 .
consists of two cycle s C and D, both of length 3 or 4, and a path P. One endpoint of P is identified with a vertex of C and the other endpoint is identified with a vertex of D. If both C and D are triangles, than P must have at least 2 edges, otherwise P may have length 0 or 1. Example: fish , X7 , X11 , X27 .
is created from a hole by adding a single chord that forms a triangle with two edges of the hole (i.e. a single chord that is a short chord). Example: house .
with n,k relatively prime and n > 2k consists of vertices a0,..,an-1 and b0,..,bn-1. ai is adjacent to aj with j-i <= k (mod n); bi is adjacent to bj with j-i < k (mod n); and ai is adjacent to bj with j-i <= k (mod n). In other words, ai is adjacent to ai-k..ai+k, and to bi-k,..bi+k-1 and bi is adjacent to ai-k+1..ai+k and to bi-k+1..bi+k-1. Example: C(3,1) = S3 , C(4,1) = X53 , C(5,1) = X72 .
consists of a clique V={v0,..,vn-1} (n>=3) and two independent sets P={p0,..pn-1} and Q={q0,..qn-1}. pi is adjacent to all vj such that j != i (mod n). qi is adjacent to all vj such that j != i-1, j != i (mod n). pi is adjacent to qi. Example: X179 .
have n nodes and an edge between every pair (v,w) of vertices with v != w. Example: triangle , K4 .
have nodes 0..n-1 and edges (i,i+1 mod n) for 0<=i<=n-1. Example: triangle , C4 , C5 , C6 , C8
are formed from a Pn+1 (that is, a path of length n) by adding a vertex that is adjacent to every vertex of the path. Example: diamond , gem , 4-fan .
is the disjoint union of G and N.
is formed from a graph G by adding an edge between two arbitrary unconnected nodes. Example: cricket .
consists of n disjoint copies of G.
is formed from the cycle Cn adding a vertex which is adjacent to precisely one vertex of the cycle. Example: paw , 4-pan , 5-pan , 6-pan .
have nodes 1..n and edges (i,i+1) for 1<=i<=n-1. The length of the path is the number of edges (n-1). Example: P3 , P4 , P5 , P6 , P7 .
is a K1,n .
are trees with 3 leaves that are connected to a single vertex of degree three with paths of length i, j, k, respectively. Example: star1,2,2 , star1,2,3 , fork , claw . This can be generalized to an unspecified number of leaves of course.
A sun is a chordal graph on 2n nodes (n>=3) whose vertex set can be partitioned into W = {w1..wn} and U = {u1..un} such that W is independent and ui is adjacent to wj iff i=j or i=j+1 (mod n). Example: S3 , S4 .
is formed from the cycle Cn adding a vertex which is adjacent to every vertex of the cycle. Example: K4 , W4 , W5 , W6 .
