Orthogonal symmetric matrices and joins of graphs

2020/12/23 by Rupert H. Levene, Levene, Rupert H., Polona Oblak +3 · 1 citation
Computer Science · Engineering · Mathematics · #05C50 #15A18 #15B10 #15B57 #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Matrix Theory and Algorithms #Spectral Theory (math.SP) #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2012.12694

openalex publication_date 2020/12/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We introduce a notion of compatibility for multiplicity matrices. This gives rise to a necessary condition for the join of two (possibly disconnected) graphs G and H to be the pattern of an orthogonal symmetric matrix, or equivalently, for the minimum number of distinct eigenvalues q of G\vee H to be equal to two. Under additional hypotheses, we show that this necessary condition is also sufficient. As an application, we prove that q(G\vee H) is either two or three when G and H are unions of complete graphs, and we characterise when each case occurs.

Cited by

• The minimum number of distinct eigenvalues of a threshold graph is at most 4

Related

• Orthogonalisability of joins of graphs
• Bordering of Symmetric Matrices and an Application to the Minimum Number of Distinct Eigenvalues for the Join of Graphs
• Two Distinct Eigenvalues from a New Graph Product
• The maximum of the minimal multiplicity of eigenvalues of symmetric matrices whose pattern is constrained by a graph
• Minimum number of distinct eigenvalues of graphs