On the minimum number of distinct eigenvalues of a threshold graph

DOI10.1016/J.LAA.2022.02.001MaRDI QIDQ2133671zbMATH OpenOpenAlexWikidataFDO

Authors Seyed Ahmad Mojallal, Shaun M. Fallat

Publication date 5 May 2022

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2110.10143

zbMATH Keywords

eigenvalue of graphsminimum number of distinct eigenvaluesstrong spectral propertythreshold graphsvertex-clique incidence matrix

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18) Inverse problems in linear algebra (15A29)

Abstract: For a graph $G$, we associate a family of real symmetric matrices, $S(G)$, where for any $AinS(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.

Recommendations

• Minimum number of distinct eigenvalues of graphs
• Sparsity of graphs that allow two distinct eigenvalues
• On the eigenvalues distribution in threshold graphs
• Eigenvalue location in threshold graphs
• Characterizing threshold graphs with k main signless Laplacian eigenvalues

Cites work

• A Nordhaus-Gaddum conjecture for the minimum number of distinct eigenvalues of a graph
• Degree maximal graphs are Laplacian integral
• Generalizations of the strong Arnold property and the minimum number of distinct eigenvalues of a graph
• scientific article; zbMATH DE number 4214203 (Why is no real title available?)
• Minimum number of distinct eigenvalues of graphs
• On the Minimum Rank Among Positive Semidefinite Matrices with a Given Graph
• On the zero forcing number of a graph involving some classical parameters
• Ordered multiplicity inverse eigenvalue problem for graphs on six vertices
• Spectral graph theory and the inverse eigenvalue problem of a graph
• The Construction of Jacobi and Periodic Jacobi Matrices With Prescribed Spectra
• The minimum rank of symmetric matrices described by a graph: a survey

Cited in

(17)

• A Nordhaus-Gaddum conjecture for the minimum number of distinct eigenvalues of a graph
• On the eigenvalues distribution in threshold graphs
• Characterizing threshold graphs with k main signless Laplacian eigenvalues
• A conjecture on the eigenvalues of threshold graphs
• Generalizations of the strong Arnold property and the minimum number of distinct eigenvalues of a graph
• Eigenvalue location in threshold graphs
• The simple graph threshold number (r,s,a,t) when r 3 is odd and a 2 is even
• Eigenvalue-free intervals of distance matrices of threshold and chain graphs
• Applications of analysis to the determination of the minimum number of distinct eigenvalues of a graph
• Minimum number of distinct eigenvalues of graphs
• Bordering of symmetric matrices and an application to the minimum number of distinct eigenvalues for the join of graphs
• Sparsity of graphs that allow two distinct eigenvalues
• Diminimal families of arbitrary diameter
• Laplacian eigenvalues of weighted threshold graphs
• On the minimum number of eigenvalues of trees of diameter seven
• The minimum number of distinct eigenvalues of a threshold graph is at most 4
• Orthogonalisability of joins of graphs

This page was built for publication: On the minimum number of distinct eigenvalues of a threshold graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2133671)