• Global
• ISGCI home
• Java
• All classes
• References
• Smallgraphs
• ✉

• 2-fan
• 2C₄
• 2K₁
• 2K₂
• 2K₃
• 2K₃ + e
• 2P₃
• 2diamond
• 3-fan
• 3-pan
• 3K₁
• 3K₂
• 4-fan
• 4-pan
• 4K₁
• 5-pan
• 5K₁
• 5K₁ + e
• 6-fan
• 6-pan
• A
• A ∪ K₁
• BW₃
• BW₄
• C(n,k)
• C₃
• C₄
• C₄ ∪ 2K₁
• C₄ ∪ K₁
• C₄ ∪ P₂
• C₅
• C₅ ∪ K₁
• C₆
• C₇
• C₇ ∪ K₁
• C₈
• C_n
• E
• G ∪ N
• G+e
• G-e
• H
• K₂
• K₂ ∪ 3K₁
• K₂ ∪ K₃
• K₂ ∪ K_1,3
• K₂ ∪ claw
• K₃
• K₃ ∪ 2K₁
• K₃ ∪ 3K₁
• K₃ ∪ P₃
• K₄
• K₄ - e
• K₄ ∪ K₁
• K₅
• K₅ - e
• K_n
• K_1,3
• K_1,4
• K_1,4+e
• K_2,2
• K_2,3
• K_3,3
• K_3,3 ∪ K₁
• K_3,3+e
• K_3,3-e
• K_n,m
• L(K_3,3)
• P
• P₂ ∪ P₃
• P₂ ∪ P₄
• P₃
• P₃ ∪ 2K₁
• P₃ ∪ P₄
• P₃ ∪ P₃
• P₄
• P₅
• P₆
• P₇
• P_n
• R
• S₃
• S₃ ∪ K₁
• S₄

• T₂
• T₃
• W₃
• W₄
• W₄ ∪ K₁
• W₅
• W₆
• W_n
• XC₁
• XC₂
• XC₃
• XC₄
• XC₅
• XC₆
• XC₇
• XC₈
• XC₉
• XC₁₀
• XC₁₁
• XC₁₂
• XC₁₃
• XF₁ⁿ
• XF₂ⁿ
• XF₃ⁿ
• XF₄ⁿ
• XF₅ⁿ
• XF₆ⁿ
• XF₇ⁿ
• XF₈ⁿ
• XF₉ⁿ
• XF₁₀ⁿ
• XF₁₁ⁿ
• XZ₁
• XZ₂
• XZ₃
• XZ₄
• XZ₅
• XZ₆
• XZ₇
• XZ₈
• XZ₉
• XZ₁₀
• XZ₁₁
• XZ₁₂
• XZ₁₃
• XZ₁₄
• XZ₁₅
• X₁
• X₂
• X₃
• X₄
• X₅
• X₆
• X₇
• X₈
• X₉
• X₁₀
• X₁₁
• X₁₂
• X₁₃
• X₁₄
• X₁₅
• X₁₇
• X₁₈
• X₁₉
• X₂₀
• X₂₁
• X₂₂
• X₂₃
• X₂₄
• X₂₅
• X₂₆
• X₂₇
• X₂₈
• X₂₉
• X₃₀
• X₃₁
• X₃₂
• X₃₃
• X₃₄
• X₃₅
• X₃₅ ∪ K₁
• X₃₆
• X₃₇

• X₃₈
• X₃₉
• X₄₀
• X₄₁
• X₄₂
• X₄₃
• X₄₄
• X₄₅
• X₄₆
• X₄₇
• X₄₈
• X₄₉
• X₅₀
• X₅₁
• X₅₂
• X₅₃
• X₅₄
• X₅₅
• X₅₆
• X₅₇
• X₅₈
• X₅₉
• X₇₀
• X₇₁
• X₇₂
• X₇₃
• X₇₄
• X₇₅
• X₇₆
• X₇₇
• X₇₉
• X₈₀
• X₈₁
• X₈₂
• X₈₃
• X₈₄
• X₈₅
• X₈₆
• X₈₇
• X₈₈
• X₈₉
• X₉₀
• X₉₁
• X₉₂
• X₉₃
• X₉₄
• X₉₅
• X₉₆
• X₉₇
• X₉₈
• X₉₉
• X₁₀₀
• X₁₀₁
• X₁₀₂
• X₁₀₃
• X₁₀₄
• X₁₀₅
• X₁₀₆
• X₁₀₇
• X₁₀₈
• X₁₀₉
• X₁₁₀
• X₁₁₁
• X₁₁₂
• X₁₁₃
• X₁₁₄
• X₁₁₅
• X₁₁₆
• X₁₁₇
• X₁₁₈
• X₁₁₉
• X₁₂₀
• X₁₂₁
• X₁₂₂
• X₁₂₃
• X₁₂₄
• X₁₂₅
• X₁₂₆
• X₁₂₇
• X₁₂₈
• X₁₂₉
• X₁₃₀
• X₁₃₁
• X₁₃₂

• X₁₃₃
• X₁₃₄
• X₁₃₅
• X₁₃₆
• X₁₃₇
• X₁₃₈
• X₁₃₉
• X₁₄₀
• X₁₄₁
• X₁₄₂
• X₁₄₃
• X₁₄₄
• X₁₄₅
• X₁₄₆
• X₁₄₇
• X₁₄₈
• X₁₄₉
• X₁₅₀
• X₁₅₁
• X₁₅₂
• X₁₅₃
• X₁₅₄
• X₁₅₅
• X₁₅₆
• X₁₅₇
• X₁₅₈
• X₁₅₉
• X₁₆₀
• X₁₆₁
• X₁₆₂
• X₁₆₃
• X₁₆₄
• X₁₆₅
• X₁₆₆
• X₁₆₇
• X₁₆₈
• X₁₆₉
• X₁₇₀
• X₁₇₁
• X₁₇₂
• X₁₇₃
• X₁₇₄
• X₁₇₅
• X₁₇₆
• X₁₇₇
• X₁₇₈
• X₁₇₉
• X₁₈₀
• X₁₈₁
• X₁₈₂
• X₁₈₃
• X₁₈₄
• X₁₈₅
• X₁₈₆
• X₁₈₇
• X₁₈₈
• X₁₈₉
• X₁₉₀
• X₁₉₁
• X₁₉₂
• X₁₉₃
• X₁₉₄
• X₁₉₅
• X₁₉₆
• X₁₉₇
• X₁₉₈
• X₁₉₉
• X₂₀₀
• X₂₀₁
• X₂₀₂
• X₂₀₃
• X₂₀₄
• X₂₀₅
• X₂₀₆
• X₂₀₇
• X₂₀₈
• X₂₀₉
• X₂₁₀
• X₂₁₂
• X₂₁₃
• X₂₁₄
• X₂₁₅
• X₂₁₆
• X₂₁₇

• X₂₁₈
• 2P₃ ∪ K₁
• P ∪ K₁
• X₃₅ ∪ K₁
• antenna
• anti-hole
• apple
• banner
• biclique
• bicycle
• building
• bull
• butterfly
• butterfly ∪ K₁
• cap
• chair
• claw
• claw ∪ 3K₁
• claw ∪ K₁
• claw ∪ triangle
• clique wheel
• co-fork ∪ K₁
• complete bipartite graph
• complete graph
• complete sun
• cricket
• cross
• cycle
• dart
• diamond
• diamond ∪ K₁
• domino
• eiffeltower
• even building
• even-cycle
• even-hole
• fan
• fish
• fork
• gem
• gem ∪ K₁
• hole
• hourglass
• house
• jewel
• kite
• kite ∪ K₁
• longhorn
• n-fan
• n-pan
• nG
• net
• net ∪ K₁
• odd anti-hole
• odd building
• odd-cycle
• odd-hole
• odd-sun
• pan
• parachute
• parapluie
• path
• paw
• rising sun
• skew-star
• spider_i,j,k
• star
• star_1,1,1,2
• star_1,1,3
• star_1,1,3 ∪ K₁
• star_1,2,2
• star_1,2,3
• star_2,2,2
• star_i,j,k
• sun
• sunlet₄
• triad
• triangle
• twin-C₅
• twin-house
• twin₃-house
• wheel

XC₁

XC₂

XC₃

XC₄

XC₅

XC₆

XC₇

XC₈

XC₉

XC₁₀

XC₁₁

XC₁₂

XC₁₃

XZ₁

XZ₂

XZ₃

XZ₄

XZ₅

XZ₆

XZ₇

XZ₈

XZ₉

XZ₁₀

XZ₁₁

XZ₁₂

XZ₁₃

XZ₁₄

XZ₁₅

XF₁ⁿ

XF₁ⁿ (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: XF₁⁰ = claw , XF₁¹ = bull . XF₁³ = X₁₇₆ .

XF₂ⁿ

XF₂ⁿ (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: XF₂⁰ = fork , XF₂¹ = net .

XF₃ⁿ

XF₃ⁿ (n >= 0) consists of a path P=p₁ ,..., p_n+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,p₁ and v is adjacent to c,p_n+1. Examples: XF₃⁰ = S₃ , XF₃¹ = rising sun .

XF₄ⁿ

XF₄ⁿ (n >= 0) consists of a path P=p₁ ,..., p_n+1 of length n, a P₃ abc and two vertices u,v. a and c are adjacent to every vertex of P, u is adjacent to a,p₁ and v is adjacent to c,p_n+1. Examples: XF₄⁰ = co-antenna , XF₄¹ = X₃₅ .

XF₅ⁿ

XF₅ⁿ (n >= 0) consists of a path P=p₁ ,..., p_n+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,p₁ and v is adjacent to b,p_n+1. Examples: XF₅⁰ = butterfly , XF₅¹ = A . XF₅² = X₄₂ . XF₅³ = X₄₇ .

XF₆ⁿ

XF₆ⁿ (n >= 0) consists of a path P=p₁ ,..., p_n+1 of length n, a P₂ ab and two vertices u,v. a and b are adjacent to every vertex of P, u is adjacent to a,p₁ and v is adjacent to b,p_n+1. Examples: XF₆⁰ = gem , XF₆¹ = H , XF₆² = X₁₇₅ .

XF₇ⁿ

XF₇ⁿ (n >= 2) consists of n independent vertices v₁ ,..., v_n and n-1 independent vertices w₁ ,..., w_n-1. w_i is adjacent to v_i and to v_i+1. A vertex a is adjacent to all v_i. A pendant edge is attached to a, v₁ , v_n.

XF₈ⁿ

XF₈ⁿ (n >= 2) consists of n independent vertices v₁ ,..., v_n ,n-1 independent vertices w₁ ,..., w_n-1, and a P₃ abc. w_i is adjacent to v_i and to v_i+1. a is adjacent to v₁ ,..., v_n-1, c is adjacent to v₂,...v_n. A pendant vertex is attached to b.

XF₉ⁿ

XF₉ⁿ (n>=2) consists of a P_2n p₁ ,..., p_2n and a C₄ abcd. p_i is adjacent to a when i is odd, and to b when i is even. A pendant vertex is attached to p₁ and to p_2n.

XF₁₀ⁿ

XF₁₀ⁿ (n >= 2) consists of a P_n+2 a₀ ,..., a_n+1, a P_n+2 b₀ ,..., b_n+1 which are connected by edges (a₁, b₁) ... (a_n, b_n).

XF₁₁ⁿ

XF₁₁ⁿ (n >= 2) consists of a P_n+1 a₀ ,..., a_n, a P_n+1 b₀ ,..., b_n and a P₂ cd. The following edges are added: (a₁, b₁) ... (a_n, b_n), (c, a_n) ... (c, b_n).

C(n,k)

with n,k relatively prime and n > 2k consists of vertices a₀,..,a_n-1 and b₀,..,b_n-1. a_i is adjacent to a_j with j-i <= k (mod n); b_i is adjacent to b_j with j-i < k (mod n); and a_i is adjacent to b_j with j-i <= k (mod n). In other words, a_i is adjacent to a_i-k..a_i+k, and to b_i-k,..b_i+k-1 and b_i is adjacent to a_i-k+1..a_i+k and to b_i-k+1..b_i+k-1. Example: C(3,1) = S₃ , C(4,1) = X₅₃ , C(5,1) = X₇₂ .

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: K₅ - e , K_3,3-e .

anti-hole

is the complement of a hole . Example: C₅ .

apple

are the (n+4)-pan s.

biclique = K_n,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 , K_1,4 , K_3,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 , X₇ , X₁₁ , X₂₇ .

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 .

clique wheel

consists of a clique V={v₀,..,v_n-1} (n>=3) and two independent sets P={p₀,..p_n-1} and Q={q₀,..q_n-1}. p_i is adjacent to all v_j such that j != i (mod n). q_i is adjacent to all v_j such that j != i-1, j != i (mod n). p_i is adjacent to q_i. Example: X₁₇₉ .

complete graph = K_n

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

complete sun

is a sun for which U is a complete graph. Example: S₃ , S₄ .

cycle = C_n

have nodes 0..n-1 and edges (i,i+1 mod n) for 0<=i<=n-1. Example: triangle , C₄ , C₅ , C₆ , C₈

even building

is a building with an even number of vertices. Example: X₃₇ .

even-cycle

is a cycle with an even number of nodes. Example: C₄ , C₆ .

even-hole

is a hole with an even number of nodes. Example: C₆ , C₈ .

fan = n-fan

are formed from a P_n+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 .

hole

is a cycle with at least 5 nodes. Example: C₅ .

nG

consists of n disjoint copies of G.

odd anti-hole

is the complement of an odd-hole . Example: C₅ .

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 , C₅ .

odd-hole

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

odd-sun

is a sun for which n is odd. Example: S₃ .

pan = n-pan

is formed from the cycle C_n adding a vertex which is adjacent to precisely one vertex of the cycle. Example: paw , 4-pan , 5-pan , 6-pan .

path = P_n

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: P₃ , P₄ , P₅ , P₆ , P₇ .

star

is a K_1,n .

star_i,j,k = triad = spider_i,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: star_1,2,2 , star_1,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 = {w₁..w_n} and U = {u₁..u_n} such that W is independent and u_i is adjacent to w_j iff i=j or i=j+1 (mod n). Example: S₃ , S₄ .

wheel = W_n

is formed from the cycle C_n adding a vertex which is adjacent to every vertex of the cycle. Example: K₄ , W₄ , W₅ , W₆ .