pipette
ENEnglish

A Cameron-Goethals-Seidel-Shult theorem for marked graphs

Chaohui Chen, Muhuo Liu, Haiying Shan, Zoran Stani\'c

Preprint

En palabras de los autores

The classical Cameron-Goethals-Seidel-Shult theorem characterizes graphs with least eigenvalue at least in terms of generalized line graphs, exceptional graphs, and root systems. In this paper, we establish a marked graph extension of this theorem. For a graph on vertices and a binary vector , we completely characterize all marked graphs such that , where denotes the all-ones matrix of order . Using representations by finite root systems, we show that every irreducible marked graph satisfying the above inequality is represented by either the root system or the exceptional root system . This leads to a complete structural characterization in terms of irreducible marked graphs, namely induced subgraphs of extended generalized line graphs, the marked graph , and exceptional graphs with all vertices marked. In the special case , our characterization reduces to the original Cameron-Goethals-Seidel-Shult theorem. The root system and extended generalized line graphs play the roles occupied by and generalized line graphs in the classical theory. We further apply the characterization to graphs whose second largest eigenvalue is at most , showing that every -markable graph satisfies this spectral condition.

Resultado principalEl resumen no menciona limitaciones.

Apareció: martes, 10 de noviembre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 5 figures