On the Spectrum of Locally Linear Graphs

2024/09/23 by Reimbay Reimbayev, Reimbayev, Reimbay
Mathematics · Computer Science · Engineering · #Graph theory and applications #Matrix Theory and Algorithms #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2409.15001

Abstract

For a locally linear graph G, which is a graph built out of triangles, it is possible to construct another graph G^* that would consist of triangles of G as vertices, while sharing (or not sharing) a common vertex between a pair of triangles would define a binary relation for edges of G^*. In this paper we show that the spectrum of G^* is uniquely defined by G. We will also show some structural similarities of these graphs; in particular, that the number of quadrilaterals and pentagons in both graphs are the same; that G^* does not contain K₄-e and K_1,4; and that G can be reconstructed from G^*.

Related

• The graphs with all but two eigenvalues equal to ± 1
• New relations for the vertex polynomial
• Spectral characterizations of two families of nearly complete bipartite graphs
• Spectral extremal graphs for fan graphs
• Geometric and spectral properties of locally tessellating planar graphs