Eigenvalue location in graphs of small clique-width

DOI10.1016/J.LAA.2018.09.015MaRDI QIDQ1625480zbMATH OpenOpenAlexFDO

Authors Carlos Hoppen, David P. Jacobs, Vilmar Trevisan, Martin Fürer

Publication date 29 November 2018

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

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

zbMATH Keywords

adjacency matrixeigenvaluesmall clique-width

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Eigenvalues, singular values, and eigenvectors (15A18)

Abstract: Finding a diagonal matrix congruent to $A-cI$ for constants $c$, where $A$ is the adjacency matrix of a graph $G$ allows us to quickly tell the number of eigenvalues in a given interval. If $G$ has clique-width $k$ and a corresponding $k$-expression is known, then diagonalization can be done in time $O(extpoly(k)n)$ where $n$ is the order of $G$.

Recommendations

• Locating the eigenvalues for graphs of small clique-width
• Eigenvalue location in cographs
• Locating eigenvalues in graphs. Algorithms and applications
• Eigenvalue location in threshold graphs
• Computing Graph Polynomials on Graphs of Bounded Clique-Width

Cites work

• \(k\)-NLC graphs and polynomial algorithms
• Clique-width minimization is NP-hard
• Complement reducible graphs
• Diffusion maps
• Eigenvalue location for chain graphs
• Eigenvalue location in cographs
• Eigenvalue location in threshold graphs
• Graph minors. II. Algorithmic aspects of tree-width
• Handle-rewriting hypergraph grammars
• scientific article; zbMATH DE number 1460605 (Why is no real title available?)
• scientific article; zbMATH DE number 878897 (Why is no real title available?)
• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Interlacing results on matrices associated with graphs
• Locating the eigenvalues for graphs of small clique-width
• Locating the eigenvalues of trees
• On certain eigenspaces of cographs
• On nested split graphs whose second largest eigenvalue is less than 1
• On the Relationship Between Clique-Width and Treewidth
• On the structure of node-label-controlled graph languages
• Recent developments on graphs of bounded clique-width
• Restrictions, extensions, and variations of NLC grammars
• Some notes on spectra of cographs.
• Some spectral properties of cographs
• Sparse regular random graphs: spectral density and eigenvectors
• Spectral distributions of adjacency and Laplacian matrices of random graphs
• The expected eigenvalue distribution of a large regular graph
• The rank of a cograph
• Upper bounds to the clique width of graphs

Cited in

(8)

• Eigenvalue location in cographs
• Locating the eigenvalues for graphs of small clique-width
• Domination and spectral graph theory
• Location of the eigenvalues of weighted graphs with a cut edge
• Locating Eigenvalues of Symmetric Matrices - A Survey
• Efficient diagonalization of symmetric matrices associated with graphs of small treewidth
• Locating eigenvalues of matrogenic graphs in linear time
• Efficient diagonalization of symmetric matrices associated with graphs of small treewidth

This page was built for publication: Eigenvalue location in graphs of small clique-width

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