Enumeration in Graphs

Counting Hamilton Cycles

Grid graphs Gm,n

number of vertices: mn
number of edges: 2mn - m - n

Example: All Hamilton cycles of a 4x5 grid


m

n

Number of Hamilton cycles

2

2

1

2

3

1

3

4

2

4

4

6

4

5

14

5

6

154

6

6

1072

6

7

5320

7

8

301384

8

8

4638576

8

9

49483138

9

10

13916993782

10

10

467260456608

10

11

10754797724124

11

12

14746957510647992

12

12

1076226888605605706

12

13

53540340738182687296

13

14

354282765498796010420944

14

14

56126499620491437281263608

14

15

6040964455632840415885507728

15

16

191678405883294971709423926242394

16

16

65882516522625836326159786165530572

Other Examples

 

Graph
G = (V,E)

|V|

|E|

Picture

Number of Hamilton cycles

PLG

21

57

gif

187420

CDG17_5

17

85

gif

3444735369

GGR4

60

240

gif

45651133223206551617074619

GridCross

196

350

gif

2257876975655608926103

torus5x7

35

70

gif

1045940

CPN

70

183

gif

223299220030163

g4x4x3

48

104

gif

3777388236

Number of Acyclic Orientations

Grid graphs Gn,n

number of vertices: n2
number of edges: 2n2 - 2n
 

n

Number of acyclic orientations

2

14

3

2398

4

5015972

5

128091434266

6

39931856138212664

7

151966368274993474937668

8

7059965159455454640307807067492

9

4003910412343921295679925280332950062686

10

27719972687144020161876951888422165049044889741764

11

2342760547300874850450641239572199781439229470255122240558188

 12

 2417072510694501304719764868037764347803356954699009024638798250225783872

 13

30442347832318153993316363543566747367446934267327196088949432823063023430339711961996 

14

4680511374972183443159989261963850946125983198615470181685685384005869425416745250316028869223632264

Other Examples

 

Graph
G = (V,E)

|V|

|E|

Picture

Number of acyclic orientations

PLG

21

57

gif

1311413510256

CDG17_5

17

85

gif

5183906636160

GGR4

60

240

gif


GridCross

196

350

gif

1955718099049291451199839701926456156142095566965904885903222385737207905521924591267440831364098

torus5x7

35

70

gif

5733622353329425800

CPN

70

183

gif


g4x4x3

48

104

gif

1029944848402835614959797246

Number of Spanning Forests

Grid graphs Gn,n

number of vertices: n2
number of edges: 2n2 - 2n
 

n

Number of spanning forests

2

15

3

3102

4

8790016

5

341008617408

6

181075508242067552

7

1315927389374152034113856

8

130877523274817580209987036404864

9

178135975585132088643635627145305047963624

10

3318089946193080260596185780557019330240985991363200

11

845810281460839114896541390288164525407725177643901666416522016

12

2950565395249172961591657535384553845267560263963092377016829595054793952256

13

140859004008895192931987026061639962680426703120315857866026068126720656133978080000184584

14

92026069649343018430487961391008623781349342824682737080877682861035128488711594595896016516348865808448



Other Examples

 

Graph
G = (V,E)

|V|

|E|

Picture

Number of spanning forests

PLG

21

57

gif

64389243886688

CDG17_5

17

85

gif

3100357578050175

GGR4

60

240

gif


GridCross

196

350

gif

19427270757243097953065904041293495067572152837130344304977487127432165953818559828103569401504350466

torus5x7

35

70

gif

44508698259611066477

CPN

70

183

gif


g4x4x3

48

104

gif

32529108625334185988512537824

Number of Independent Vertex Sets

Grid graphs Gn,n

number of vertices: n2
number of edges: 2n2 - 2n
 

n

number of independent vertex sets

2

7

3

63

4

1234

5

55447

6

5598861

7

1280128950

8

660647962955

9

770548397261707

10

2030049051145980050

11

12083401651433651945979

12

162481813349792588536582997

13

4935961285224791538367780371090

14

338752110195939290445247645371206783

15

52521741712869136440040654451875316861275

16

18396766424410124752958806046933947217821482942

17

14557601701834111295974187104248827765798599152358303

18

26024585612650837861658126921792857026992497268285945167621

19

105105055066577962012604229608317915229737651637019975757755051314

20

958979036662929619406859624886958746851620546557485230898539651354907499

21

19766982580727525559447459703066410506378295841376040664015562851325369819076327

22

920486427724231647653646535134255190048558085587696509535085179014710020739303637413062

23

96836737362332577228126233146266027907220602904916569863928397932638147313462817836132159477643

24

23014876830102973080295375510481185265791418130718634637816237986620978856344595418898906840911239867869



Other Examples

 

Graph
G = (V,E)

|V|

|E|

Picture

Number of independent vertex sets

PLG

21

57

gif

1883

CDG17_5

17

85

gif

69

GGR4

60

240

gif


GridCross

196

350

gif

959058366353218549120774774618950845

torus5x7

35

70

gif

1511931

CPN

70

183

gif

162761412351

g4x4x3

48

104

gif


Number of Cycle Covers

= number of ways to cover G by vertex disjoint cycles

Grid graphs Gm,n

m

n

number of cycle covers

2

2

1

2

3

1

3

4

3

4

4

18

4

5

54

5

6

1140

6

6

13903

6

7

99051

7

8

13049563

8

8

360783593

8

9

6044482889

9

10

4738211572702

10

10

303872744726644

10

11

11986520595161863

11

12

54755153078468134960

12

12

8217125138015950451626

12

13

764291947227525464744293

13

14

20119942924108379011391597989

14

14

7095967027221343377167292602835

14

15

1558052539448513320447263528275071

15

16

234788223520702255614480389250160811898

16

16

195081705501438193439250404333039349462635

16

17

101199388044301804167035198499446336399419451

17

18

86918369741985767628242106496018767545685968221295

18

18

170400931523966165754313513175663906434875251822099185



Other Examples

 

Graph
G = (V,E)

|V|

|E|

Picture

Number of cycle covers

PLG

21

57

gif

578218

CDG17_5

17

85

gif

7494022727

GGR4

60

240

gif

852773355003399298441058984

GridCross

196

350

gif

4425127092980431636475240207

torus5x7

35

70

gif

4831612

CPN

70

183

gif

13413617257992766

g4x4x3

48

104

gif

31995940992