## Graphs ordered alphabetically

Note that complements are usually not listed. So for e.g. co-fork, look for fork.

## Graphs ordered by number of vertices

### 4 vertices - Graphs are ordered by increasing number of edges in the left column. The list contains all 11 graphs with 4 vertices.

#### P4Ch

Self complementary

### 5 vertices - Graphs are ordered by increasing number of edges in the left column. The list contains all 34 graphs with 5 vertices.

#### bullD{O

Self complementary

#### C5Dhc

Self complementary

### 8 vertices - Graphs are ordered by increasing number of edges in the left column. The list does not contain all graphs with 8 vertices.

#### S4G~fB@_

Self complementary

#### X186Ghqihc

Self complementary

#### X160GjTJwC

Self complementary

### 9 vertices - Graphs are ordered by increasing number of edges in the left column. The list does not contain all graphs with 9 vertices.

#### X202 = L(K3,3)H{S{aSf

Self complementary

### Configurations XC

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.

### Configurations XZ

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 XF

Families are normally specified as XFif(n) where n implicitly starts from 0. For example, XF12n+3 is the set XF13, XF15, XF17...

#### XF1n

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

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

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

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

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

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

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

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

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

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

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).

### General families

#### anti-hole

is the complement of a hole . Example: C5 .

#### apple

are the (n+4)-pan s.

#### biclique = Kn,m = complete bipartite graph

consist of a non-empty independent set U of n vertices, and a non-empty 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 .

#### bicycle

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 .

#### building = cap

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 .

#### C(n,k)

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 .

#### clique wheel

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 .

#### complete graph = Kn

have n nodes and an edge between every pair (v,w) of vertices with v != w. Example: triangle , K4 .

#### complete sun

is a sun for which U is a complete graph. Example: S3 , S4 .

#### cycle = Cn

have nodes 0..n-1 and edges (i,i+1 mod n) for 0<=i<=n-1. Example: triangle , C4 , C5 , C6 , C8

#### even building

is a building with an even number of vertices. Example: X37 .

#### even-cycle

is a cycle with an even number of nodes. Example: C4 , C6 .

#### even-hole

is a hole with an even number of nodes. Example: C6 , C8 .

#### fan = n-fan

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 .

#### G ∪ N

is the disjoint union of G and N.

#### G+e

is formed from a graph G by adding an edge between two arbitrary unconnected nodes. Example: cricket .

#### G-e

is formed from a graph G by removing an arbitrary edge. Example: K5 - e , K3,3-e .

#### hole

is a cycle with at least 5 nodes. Example: C5 .

#### nG

consists of n disjoint copies of G.

#### odd anti-hole

is the complement of an odd-hole . Example: C5 .

#### odd building

is a building with an odd number of vertices. Example: house .

#### odd-cycle

is a cycle with an odd number of nodes. Example: triangle , C5 .

#### odd-hole

is a hole with an odd number of nodes. Example: C5 .

#### odd-sun

is a sun for which n is odd. Example: S3 .

#### pan = n-pan

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 .

#### path = Pn

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 .

#### stari,j,k = triad = spideri,j,k

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 . The generalisation to an unspecified number of leaves are known as spiders.

#### sun

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 .

#### wheel = Wn

is formed from the cycle Cn adding a vertex which is adjacent to every vertex of the cycle. Example: K4 , W4 , W5 , W6 .