2021/10/19 by Fallat, Shaun, Mojallal, Seyed Ahmad · 1 citation
#05C50 #15A29 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2110.10143
For a graph G, we associate a family of real symmetric matrices, S(G), where for any A∈ S(G), the location of the nonzero off-diagonal entries of A are governed by the adjacency structure of G. Let q(G) be the minimum number of distinct eigenvalues over all matrices in S(G). In this work, we give a characterization of all connected threshold graphs G with q(G)=2. Moreover, we study the values of q(G) for connected threshold graphs with trace 2, 3, n-2, n-3, where n is the order of threshold graph. The values of q(G) are determined for all connected threshold graphs with 7 and 8 vertices with two exceptions. Finally, a sharp upper bound for q(G) over all connected threshold graph G is given.