Graph details

Graph # 34222

Adjacency matrix

[Too large to display]

Adjacency list

[Too large to display]

HoG graph id

34222

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.

Comments

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). http://www.win.tue.nl/~aeb/graphs/integral_trees.html, http://www.win.tue.nl/~aeb/preprints/small_itrees.pdf

Also appears in A. E. Brouwer and W. H. Haemers, "Spectra of Graphs", Springer, 2011, section 5.7 exercise 1, page 88. http://www.win.tue.nl/~aeb/2WF02/spectra.pdf

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