Graph details

Graph # 34222

Adjacency matrix

[Too large to display]

Adjacency list

[Too large to display]

HoG graph id


Graph name

Integral Tree N=31 (Brouwer's #17)

Graph submitted by

Kevin Ryde

Invariant values

The definitions of the invariants can be found here.
Invariant Value Invariant Value
Acyclic Yes Index 3
Algebraic Connectivity 0.108 Laplacian Largest Eigenvalue 7.826
Average Degree 1.935 Longest Induced Cycle undefined
Bipartite Yes Longest Induced Path 6
Chromatic Index 6 Matching Number 10
Chromatic Number 2 Maximum Degree 6
Circumference undefined Minimum Degree 1
Claw-Free No Minimum Dominating Set 10
Clique Number 2 Number of Components 1
Connected Yes Number of Edges 30
Density 0.065 Number of Triangles 0
Diameter 6 Number of Vertices 31
Edge Connectivity 1 Planar Yes
Eulerian No Radius 3
Genus 0 Regular No
Girth undefined Second Largest Eigenvalue 2
Hamiltonian No Smallest Eigenvalue -3
Independence Number 21 Vertex Connectivity 1

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


Posted by Kevin Ryde at Jan 5, 2020 1:50 AM.
This tree is integral, meaning all roots of the characteristic polynomial of its adjacency matrix are integers. It was found by Brouwer and is one of 3 integral trees of n=31 vertices.

A. E. Brouwer, "Small Integral Trees", The Electronic Journal of Combinatorics, volume 15, 2008. Figure 1 picture, and table 1 depths and spectrum (tree #17, the new n=31).,

Also appears in A. E. Brouwer and W. H. Haemers, "Spectra of Graphs", Springer, 2011, section 5.7 exercise 1, page 88.

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