Trees with very few eigenvalues

Autor:	Robert A. Beezer
Rok vydání:	1990
Předmět:	Discrete mathematics Dense graph 1-planar graph Modular decomposition Combinatorics Indifference graph Pathwidth Chordal graph Discrete Mathematics and Combinatorics Cograph Geometry and Topology Graph product MathematicsofComputing_DISCRETEMATHEMATICS Mathematics
Zdroj:	Journal of Graph Theory. 14:509-517
ISSN:	1097-0118 0364-9024
DOI:	10.1002/jgt.3190140415
Popis:	The number of distinct eigenvalues of the adjacency matrix of a graph is bounded below by the diameter of the graph plus one. Many graphs that achieve this lower bound exhibit much symmetry, for example, distance-transitive and distance-regular graphs. Here we provide a recursive construction that will create graphs having the fewest possible eigenvalues. This construction is best at creating trees, but will also create cyclic graphs meeting the lower bound. Unlike the graphs mentioned above, many of the graphs constructed do not exhibit large amounts of symmetry. A corollary allows us to determine the values and multiplicities of all the nonsimple eigenvalues of the constructed graph.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::f9d344ac74c936ec4ede24b36b40c294 https://doi.org/10.1002/jgt.3190140415 Zobrazit plný text záznamu Plný text