Contents

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

3 vertices - Graphs are ordered by increasing number of edges in the left column.

3K1 = co-triangleB?

3K1

triangle = K3 = C3Bw

triangle

P3BO

co-P3

P3Bg

P3

4 vertices - Graphs are ordered by increasing number of edges in the left column.

4K1 = K4C?

4K1

K4 = W3C~

K4

co-diamondCC

co-diamond

diamond = K4 - e = 2-fanCz

diamond

co-pawCE

co-paw

paw = 3-panCx

paw

2K2 = C4CK

2K2

C4 = K2,2Cr

C4

claw = K1,3Cs

claw

co-clawCJ

co-claw

P4Ch

P4

Self complementary

5 vertices - Graphs are ordered by increasing number of edges in the left column.

5K1 = K5D??

5K1

K5D~{

K5

K5 - e = 5K1 + e = K2 ∪ 3K1D?O

co-K5-e

K5 - eD~k

K5-e

P3 ∪ 2K1Do?

P3U2K1

P3 ∪ 2K1DN{

co-P3U2K1

W4DQ?

co-W4

W4Dl{

W4

claw ∪ K1Ds?

clawUK1

claw ∪ K1DJ{

co-clawUK1

P2 ∪ P3D`C

P2UP3

P2 ∪ P3D]w

co-P2UP3

co-gemDU?

co-gem

gem = 3-fanDh{

gem

K3 ∪ 2K1Dw?

K3U2K1

K3 ∪ 2K1DF{

co-K3U2K1

K1,4Ds_

K14

K1,4 = K4 ∪ K1DJ[

K4UK1

co-butterfly = C4 ∪ K1DBW

co-butterfly

butterfly = hourglassD{c

butterfly

fork = chairDiC

fork

co-fork = kite = co-chair = chairDTw

kite

co-dartDGw

co-dart

dartDvC

dart

P5DhC

P5

house = P5DUw

house

K2 ∪ K3 = K2,3D`K

co-K23

K2,3D]o

K23

P = 4-pan = bannerDrG

P

PDKs

co-P

bullD{O

bull

Self complementary

cricket = K1,4+eDiS

cricket

co-cricket = diamond ∪ K1DTg

co-cricket

C5Dhc

C5

Self complementary

6 vertices - Graphs are ordered by increasing number of edges in the left column.

3K2E`?G

3K2

3K2E]~o

co-3K2

X197 = P3P3EgC?

X197

X197EVzw

co-X197

P2 ∪ P4Eh?G

P2UP4

P2 ∪ P4EU~o

co-P2UP4

2P3EgCG

2P3

2P3EVzo

co-2P3

C4 ∪ 2K1El??

C4U2K1

C4 ∪ 2K1EQ~w

co-C4U2K1

K2 ∪ claw = K2 ∪ K1,3Es?G

K2Uclaw

K2 ∪ clawEJ~o

co-K2Uclaw

cross = star1,1,1,2EiD?

cross

co-crossETyw

co-cross

HEgSG

H

HEVjo

co-H

C4 ∪ P2El?G

C4UP2

C4 ∪ P2EQ~o

co-C4UP2

E = star1,2,2EhC_

E

E = co-star1,2,2EUzW

co-E

K3 ∪ P3EWCW

K3UP3

K3,3+eEfz_

K33+e

X198 = P ∪ K1EhK?

X198

X198EUrw

co-X198

P6EhCG

P6

P6EUzo

co-P6

W5 = C5 ∪ K1EUW?

co-W5

W5Ehfw

W5

X172 = star1,1,3EhCO

X172

X172EUzg

co-X172

co-fork ∪ K1 = kite ∪ K1EDaW

kiteUK1

co-fork ∪ K1 = kite ∪ K1Ey\_

co-kiteUK1

butterfly ∪ K1E{c?

butterflyUK1

butterfly ∪ K1EBZw

co-butterflyUK1

co-4-fanEUw?

co-4fan

4-fanEhFw

4fan

AEhSG

A

AEUjo

co-A

RElCO

R

REQzg

co-R

2K3 = K3,3EwCW

2K3

K3,3EFz_

K33

C6EhEG

C6

C6EUxo

co-C6

X98EQUO

co-X98

X98 = twin3-houseElhg

X98

net = S3EDbO

net

S3Ey[g

S3

X18ElCG

X18

X18EQzo

co-X18

5-panEhcG

5pan

5-panEUZo

co-5pan

X166EhD_

X166

X166EUyW

co-X166

X169EhGg

X169

X169EUvO

co-X169

X84ElD?

X84

X84EQyw

co-X84

X95EXCW

X95

X95Eez_

co-X95

gem ∪ K1Eq{?

gemUK1

gem ∪ K1ELBw

co-gemUK1

W4 ∪ K1EQBw

co-W4UK1

W4 ∪ K1El{?

W4UK1

X37EhMG

X37

X37EUpo

co-X37

fishErCW

fish

co-fishEKz_

co-fish

dominoErGW

domino

co-dominoEKv_

co-domino

twin-C5EhdG

twinC5

co-twin-C5 = twin-C5EUYo

co-twinC5

X58EUwG

co-X58

X58EhFo

X58

2K3 + e = K3,3-eEwCw

co-K33-e

K3,3-eEFz?

K33-e

X5EAxo

co-X5

X5E|EG

X5

antennaEjCg

antenna

co-antennaESzO

co-antenna

X45EhQg

X45

X45EUlO

co-X45

co-twin-house = twin-houseEQKw

co-twin-house

twin-houseElr?

twin-house

X167EhTO

X167

X167EUig

co-X167

X168EhPo

X168

X168EUmG

co-X168

X170EhGw

X170

X170EUv?

co-X170

X171EhCw

X171

X171EUz?

co-X171

X96EgTg

X96

X96EViO

co-X96

X163Ehp_

X163

X163EUMW

co-X163

7 vertices - Graphs are ordered by increasing number of edges in the left column.

claw ∪ 3K1Fs???

clawU3K1

claw ∪ 3K1FJ~~w

co-clawU3K1

P3 ∪ P4Fh?GG

P3UP4

P3 ∪ P4FU~vo

co-P3UP4

X177 = star1,1,3 ∪ K1FhCO?

X177

X177FUznw

co-X177

A ∪ K1Fr?__

AUK1

A ∪ K1FK~^W

co-AUK1

net ∪ K1FjGO?

netUK1

net ∪ K1FSvnw

co-netUK1

T2 = star2,2,2FhC_G

T2

T2FUz^o

co-T2

P7FhCGG

P7

P7FUzvo

co-P7

star1,2,3 = skew-starFhCG_

skewstar

star1,2,3FUzvW

co-skewstar

X85FhD?_

X85

X85FUy~W

co-X85

claw ∪ triangleFs?GW

clawUtriangle

claw ∪ triangleFJ~v_

co-clawUtriangle

6-panFhEGG

6pan

6-panFUxvo

co-6pan

C7FhCKG

C7

C7FUzro

co-C7

X12FKdE?

co-X12

X12FrYxw

X12

X41FhO_W

X41

X41FUn^_

co-X41

longhornFhCH_

longhorn

co-longhornFUzuW

co-longhorn

X2FhDOG

X2

X2FUyno

co-X2

X6Fl_GO

X6

X6FQ^vg

co-X6

X130FhDAG

X130

X130FUy|o

co-X130

eiffeltowerFhCoG

eiffel

co-eiffeltowerFUzNo

co-eiffel

X11FKde?

co-X11

X11FrYXw

X11

X20FhCiG

X20

X20FUzTo

co-X20

X38FhCKg

X38

X38FUzrO

co-X38

X3FrGX?

X3

X3FKvew

co-X3

X7Fl_GW

X7

X7FQ^v_

co-X7

X27FlGHG

X27

X27FQvuo

co-X27

X30FhOgW

X30

X30FUnV_

co-X30

X173FhEKG

X173

X173FUxro

co-X173

X175FUwK?

co-X175

X175FhFrw

X175

X90FUWPG

co-X90

X90Fhfmo

X90

X106FSwq?

co-X106

X106FjFLw

X106

X127F`GV_

X127

X127F]vgW

co-X127

X128FUg`G

co-X128

X128FhV]o

X128

X134FhDWG

X134

X134FUyfo

co-X134

X162FsiOG

co-X162

X162FJTno

X162

K3,3 ∪ K1FFz_?

K33UK1

K3,3 ∪ K1FwC^w

co-K33UK1

S3 ∪ K1Fy[g?

S3UK1

S3 ∪ K1FDbVw

co-S3UK1

X42FExaO

co-X42

X42FxE\g

X42

X32FhFh?

X32

X32FUwUw

co-X32

X9FhEhO

X9

X9FUxUg

co-X9

X8FrGWW

X8

X8FKvf_

co-X8

X33FhEj?

X33

X33FUxSw

co-X33

co-rising sunF?M]W

co-risingsun

rising sunF~p`_

risingsun

X39FhhOW

X39

X39FUUn_

co-X39

X46FUhS_

co-X46

X46FhUjW

X46

X15FQFb_

co-X15

X15Flw[W

X15

W6FLv_?

co-W6

W6FqG^w

W6

BW3FqG[o

BW3

BW3FLvbG

co-BW3

parapluie = co-parachuteFAYFo

parapluie

parachute = co-parapluieF|dwG

parachute

X82FGrEg

co-X82

X82FvKxO

X82

X176FhCJo

X176

X176FUzsG

co-X176

X87FUYT?

co-X87

X87Fhdiw

X87

X88FDbRO

co-X88

X88Fy[kg

X88

X89FUWsG

co-X89

X89FhfJo

X89

X92FErF?

X92

X92FxKww

co-X92

X97F?vFO

co-X97

X97F~Gwg

X97

X184F_Kz_

co-X184

X184F^rCW

X184

X103FEPqg

co-X103

X103FxmLO

X103

X105FUwo_

co-X105

X105FhFNW

X105

X129FhCeo

X129

X129FUzXG

co-X129

X132FhDEg

X132

X132FUyxO

co-X132

X159FsioG

co-X159

X159FJTNo

X159

X199FhCNo

X199

X199FUzoG

co-X199

co-6-fanFUzo?

co-6fan

6-fanFhCNw

6fan

X200FUxoG

co-X200

X200FhENo

X200

X13FlwWG

X13

X13FQFfo

co-X13

X36FhhWW

X36

X36FUUf_

co-X36

X35FhFj?

X35

X35FUwSw

co-X35

X70FuwGW

co-X70

X70FHFv_

X70

X14FQFf_

co-X14

X14FlwWW

X14

X34FDauo

co-X34

X34Fy\HG

X34

X40FhhoW

X40

X40FUUN_

co-X40

X1FDa]o

co-X1

X1Fy\`G

X1

X10FrGXW

X10

X10FKve_

co-X10

X17FKzc_

co-X17

X17FrCZW

X17

X31FhFx?

X31

X31FUwEw

co-X31

X86FUWZG

co-X86

X86Fhfco

X86

X93FErf?

X93

X93FxKWw

co-X93

X99FFzc?

X99

X99FwCZw

co-X99

X100FgCNw

X100

X100 = 2P3 ∪ K1FVzo?

co-X100

X101FwC\g

X101

X101FFzaO

co-X101

X102FgC^g

X102

X102FVz_O

co-X102

X104FxELO

X104

co-X104FExqg

co-X104

X107FUPqg

co-X107

X107FhmLO

X107

X133FU@]W

co-X133

X133Fh}`_

X133

8 vertices - Graphs are ordered by increasing number of edges in the left column.

X108 = C7 ∪ K1GhCKG?

co-X108

X108GUzrv{

X108

2C4Gl?GGS

2C4

2C4GQ~vvg

co-2C4

X19GhCI@C

X19

X19GUzt}w

co-X19

sunlet4Gl`@?_

sunlet4

sunlet4GQ]}~[

co-sunlet4

C8GhCGKC

C8

C8GUzvrw

co-C8

X71GiGWGO

X71

X71GTvfvk

co-X71

X77GxEG_G

X77

X77GExv^s

co-X77

X165Gl`H?_

X165

X165GQ]u~[

co-X165

X152GO?O~C

X152

X152Gn~n?w

co-X152

X74G?pk`c

X74

X74G~MR]W

co-X74

X180 = 2diamondG|?GWS

X180

X180GA~vfg

co-X180

X164Gl`H?c

X164

X164GQ]u~W

co-X164

X29G?bFF_

X29

X29G~[ww[

co-X29

X117Gk?Xoc

co-X117

X117GR~eNW

X117

X125 = X35 ∪ K1GGGqHw

co-X125

X125GvvLuC

X125

X22GhSIhC

X22

X22GUjtUw

co-X22

X26GkQAhS

X26

X26GRl|Ug

co-X26

X25GDhXGo

X25

X25GyUevK

co-X25

X181G|GGWS

X181

X181GAvvfg

co-X181

X182Gh{GGK

X182

X182GUBvvo

co-X182

X110 = X35 ∪ K1GBTHqC

co-X110

X110G{iuLw

X110

X114GgGsHw

co-X114

X114GVvJuC

X114

X116GgKkpC

co-X116

X116GVrRMw

X116

X53GUxQS_

co-X53

X53GhElj[

X53

X28GlUad?

X28

X28GQh\Y{

co-X28

X185GhRHhC

X185

X185GUkuUw

co-X185

X188GQLTUG

co-X188

X188Glqihs

X188

X79GhELQg

X79

X79GUxqlS

co-X79

X111GhKMKg

X111

X111GUrprS

co-X111

X115GkGohw

co-X115

X115GRvNUC

X115

X119G@zsT?

co-X119

X119G}CJi{

X119

X124GRTKqC

co-X124

X124GkirLw

X124

X126GSW]J_

X126

X126Gjf`s[

co-X126

X131GJEw[_

X131

X131GsxFb[

co-X131

X142Gl_fa_

X142

X142GQ^W\[

co-X142

X150GQMWD[

co-X150

X150Glpfy_

X150

X52GUxQU_

co-X52

X52GhElh[

X52

X80GhELQk

X80

X80GUxqlO

co-X80

X47GhEhhW

X47

X47GUxUUc

co-X47

X48GhElHW

X48

X48GUxQuc

co-X48

X178GnfB@_

X178

X178GOW{}[

co-X178

X187GQLTUW

co-X187

X187Glqihc

X187

X189GhdWJS

X189

X189GUYfsg

co-X189

X192GUWmdG

co-X192

X192GhfPYs

X192

X193GUXPQ[

co-X193

X193Gheml_

X193

X109GhCMLw

X109

X109GUzpqC

co-X109

X118G[bpoc

co-X118

X118Gb[MNW

X118

X120GUrpb?

co-X120

X120GhKM[{

X120

X121GxKJKg

X121

X121GErsrS

co-X121

X123Gbe@s[

co-X123

X123G[X}J_

X123

X135GHPjn?

X135

X135GumSO{

co-X135

X137GEmSO{

co-X137

X137GxPjn?

X137

X143Gl_fq_

X143

X143GQ^WL[

co-X143

X144Gl`fa_

X144

X144GQ]W\[

co-X144

X149GQMWL[

co-X149

X149Glpfq_

X149

X151GQ]WD[

co-X151

X151Gl`fy_

X151

X161GSiSFw

co-X161

X161GjTjwC

X161

X50GhEhh[

X50

X50GUxUU_

co-X50

X51GhElH[

X51

X51GUxQu_

co-X51

X49GhElhW

X49

X49GUxQUc

co-X49

S4G~fB@_

S4

Self complementary

X186Ghqihc

X186

Self complementary

X190GVWs]G

X190

X190GgfJ`s

co-X190

X191GhfPYS

X191

X191GUWmdg

co-X191

X83GjbiJC

X83

X83GS[Tsw

co-X83

X112GjCMNW

X112

X112GSzpoc

co-X112

X113GxCJLw

X113

X113GEzsqC

co-X113

X122G{guHo

X122

X122GBVHuK

co-X122

X136GXPjn?

X136

X136GemSO{

co-X136

X145Glpfa_

X145

X145GQMW\[

co-X145

X146Gl`fi_

X146

X146GQ]WT[

co-X146

X147Gh`fy_

X147

X147GU]WD[

co-X147

X148Gl`fq_

X148

X148GQ]WL[

co-X148

X160GjTJwC

X160

Self complementary

9 vertices - Graphs are ordered by increasing number of edges in the left column.

X94HgSG?S@

X94

X94HVjv~j}

co-X94

X91HgCg?Cd

X91

X91HVzV~zY

co-X91

X73HhEI?_C

X73

X73HUxt~^z

co-X73

X43HhD@GcA

X43

X43HUy}vZ|

co-X43

X21HhSIgC_

X21

X21HUjtVz^

co-X21

X138HQr?OJK

X138

X138HlK~nsr

co-X138

X24HLCgLS@

X24

X24HqzVqj}

co-X24

BW4HhCGKEi

BW4

BW4HUzvrxT

co-BW4

X139HQr?OJk

X139

X139HlK~nsR

co-X139

X141HQR?OJm

X141

X141Hlk~nsP

co-X141

X23HhSIkCa

X23

X23HUjtRz\

co-X23

X140HQr?OJm

X140

X140HlK~nsP

co-X140

X179H{OebQc

X179

X179HBnX[lZ

co-X179

X154HO?O~Mr

X154

X154Hn~n?pK

co-X154

X56HUxQScB

co-X56

X56HhEljZ{

X56

X153HO?O~Nr

X153

X153Hn~n?oK

co-X153

X201H~|_{A?

X201

X201H?A^B|~

co-X201

X55HUxQScZ

co-X55

X55HhEljZc

X55

X54HUxQSdJ

co-X54

X54HhEljYs

X54

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

X202

Self complementary

10 vertices - Graphs are ordered by increasing number of edges in the left column.

X81IkCOK?@A?

X81

T3IhCGG_@?G

T3

X75IhEI@?CA?

X75

X75IUxt}~z|w

co-X75

X44IhCH?cA?W

X44

X76IhEI@CCAG

X76

X76IUxt}zz|o

co-X76

X183IgCNwC@?W

X183

X183IVzoFz}~_

co-X183

X174IheAHCPBG

X174

X174IUX|uzm{o

co-X174

X72IheMB?oE?

X72

X72IUXp{~Nxw

co-X72

X4IhEFHCxAG

X4

X4IUxwuzE|o

co-X4

X194IAzpsX_WG

X194

X194I|CMJe^fo

co-X194

X195IzKWWMBoW

X195

X195ICrffp{N_

co-X195

X155In~mB?WB?

co-X155

X155IO?P{~f{w

X155

X156In~mB?WR?

co-X156

X156IO?P{~fkw

X156

X157IO?Pk~fkw

X157

X157In~mR?WR?

co-X157

X158In|mR?WR?

co-X158

X158IOAPk~fkw

X158

11 vertices - Graphs are ordered by increasing number of edges in the left column.

X59JhC?GC@?HA?

X59

X57JhEljXz{@y_

X57

13 vertices - Graphs are ordered by increasing number of edges in the left column.

X203LhEH?C@CG?_@A@

X203

X196L~[ww[F?{BwFwF

X196

X196L?bFFbw~B{FwFw

co-X196

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.

XC1

XC1

XC2

XC2

XC3

XC3

XC4

XC4

XC5

XC5

XC6

XC6

XC7

XC7

XC8

XC8

XC9

XC9

XC10

XC10

XC11

XC11

XC12

XC12

XC13

XC13

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

XZ1

XZ1

XZ2

XZ2

XZ3

XZ3

XZ4

XZ4

XZ5

XZ5

XZ6

XZ6

XZ7

XZ7

XZ8

XZ8

XZ9

XZ9

XZ10

XZ10

XZ11

XZ11

XZ12

XZ12

XZ13

XZ13

XZ14

XZ14

XZ15

XZ15

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

XF1

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

XF2

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

XF3

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

XF4

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

XF5

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

XF6

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

XF7

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

XF8

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

XF9

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

XF10

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

XF11

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

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 .

star

is a K1,n .

stari,j,k = triad

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.

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 .