Original scientific paper

Characterization of Trivalent Graphs with Minimal Eigenvalue Gap

Clemens Brand
Barry Guiduli
Wilfried Imrich

Abstract

Among all trivalent graphs on n vertices, let Gn be one with the smallest possible eigenvalue gap. (The eigenvalue gap is the difference between the two largest eigenvalues of the adjacency
matrix; for regular graphs, it equals the second smallest eigenvalue of the Laplacian matrix.) We show that Gn is unique for each n and has maximum diameter. This extends work of Guiduli and solves a conjecture implicit in a paper of Bussemaker, Čobeljić, Cvetković and Seidel. Depending on n, the graph Gn may not be the only one with maximum diameter. We thus also determine all cubic graphs with maximum diameter for a given number n of vertices.

Keywords

trivalent graphs; eigenvalue gap; Laplacian matrix

Hrčak ID:

12850

URI

https://hrcak.srce.hr/12850

Publication date:

12.6.2007.

Visits: 1.440 *