Graph details

Graph # 34219

Adjacency matrix

000000000001000
000000000000001
000000000000010
000010000000000
000100000000000
000000000010000
000000001000000
000000000100000
000000100000001
000000010000010
000001000000100
100000000000110
000000000011001
001000000101000
010000001000100

Adjacency list

1: 12
2: 15
3: 14
4: 5
5: 4
6: 11
7: 9
8: 10
9: 7 15
10: 8 14
11: 6 13
12: 1 13 14
13: 11 12 15
14: 3 10 12
15: 2 9 13

HoG graph id

34219

Graph name

Knuth 7.2.1.6 Example Forest

Graph submitted by

Kevin Ryde

Invariant values

The definitions of the invariants can be found here.
Invariant Value Invariant Value
Acyclic Yes Index 2.272
Algebraic Connectivity 0 Laplacian Largest Eigenvalue 5.017
Average Degree 1.733 Longest Induced Cycle undefined
Bipartite Yes Longest Induced Path 7
Chromatic Index 3 Matching Number 7
Chromatic Number 2 Maximum Degree 3
Circumference undefined Minimum Degree 1
Claw-Free No Minimum Dominating Set 7
Clique Number 2 Number of Components 2
Connected No Number of Edges 13
Density 0.124 Number of Triangles 0
Diameter infinity Number of Vertices 15
Edge Connectivity 0 Planar Yes
Eulerian No Radius undefined
Genus undefined Regular No
Girth undefined Second Largest Eigenvalue 1.812
Hamiltonian No Smallest Eigenvalue -2.272
Independence Number 8 Vertex Connectivity 0

A table row rendered like this indicates that the graph is marked as being interesting for that invariant.

Comments

Posted by Kevin Ryde at Dec 31, 2019 1:08 AM.
Appears in Knuth 4A section 7.2.1.6 as an example ordered forest.

Donald E. Knuth, "The Art of Computer Programming", volume 4A, section 7.2.1.6, at "equation" 2. Also pre-fascicle 4A "draft of section 7.2.1.6", page 1, http://www-cs-faculty.stanford.edu/~knuth/fasc4a.ps.gz

You need to be logged in to be able to add comments.