Spectral properties of cographs and P₅-free graphs

DOI10.1080/03081087.2018.1466865MaRDI QIDQ4967261zbMATH OpenOpenAlexFDO

Authors E. Ghorbani

Publication date 3 July 2019

Published in Linear and Multilinear Algebra (Search for Journal in Brave)

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

zbMATH Keywords

adjacency matrixeigenvaluemultiplicitythreshold graphcograph\(P_5\)-free graph

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Structural characterization of families of graphs (05C75)

Abstract: A cograph is a simple graph which contains no path on 4 vertices as an induced subgraph. We consider the eigenvalues of adjacency matrices of cographs and prove that a graph $G$ is a cograph if and only if no induced subgraph of $G$ has an eigenvalue in the interval $(-1,0)$. It is also shown that the multiplicity of any eigenvalue of a cograph $G$ does not exceed the sum of multiplicities of $0$ and $-1$ as eigenvalues of $G$. We introduce a partial order on the vertex set of graphs $G$ in terms of inclusions among the open and closed neighborhoods of vertices, and conjecture that the multiplicity of any eigenvalue of a cograph $G$ except for $0,-1$ does not exceed the maximum size of an antichain with respect to that partial order. In two extreme cases (in particular for threshold graphs), the conjecture is shown to be true. Finally, we give a simple proof for the result that bipartite $P_5$-free graphs have no eigenvalue in the intervals $(-1/2,0)$ and $(0,1/2)$.

Recommendations

• Some spectral properties of cographs
• Cographs: eigenvalues and Dilworth number
• Some notes on spectra of cographs.
• On certain eigenspaces of cographs
• Multiplicity of eigenvalues of cographs

Cites work

• scientific article; zbMATH DE number 740754 (Why is no real title available?)
• A time-optimal solution for the path cover problem on cographs.
• Chromatic number of \(P_5\)-free graphs: Reed's conjecture
• Cographs: eigenvalues and Dilworth number
• Complement reducible graphs
• Dacey Graphs
• Dominating cliques in \(P_ 5\)-free graphs
• Dominating subgraphs in graphs with some forbidden structures
• Domination, coloring and stability in \(P_5\)-reducible graphs
• Eigenvalue location in threshold graphs
• Eigenvalues and energy in threshold graphs
• Graph Classes: A Survey
• Graphs whose adjacency matrices have rank equal to the number of distinct nonzero rows
• On 3-colorable \(P_5\)-free graphs
• On a class of posets and the corresponding comparability graphs
• On a property of the class of n-colorable graphs
• On certain eigenspaces of cographs
• On maximum independent sets in \(P_{5}\)-free graphs
• On the rank of a cograph
• Some notes on spectra of cographs.
• Some spectral properties of cographs
• Spectra of graphs
• The rank of a cograph
• Threshold graphs and related topics
• Transitiv orientierbare Graphen

Cited in

(16)

• Eigenvalue-free interval for Seidel matrices of cographs
• Seidel matrices, Dilworth number and an eigenvalue-free interval for cographs
• A spectral condition for the existence of a pentagon in non-bipartite graphs
• Eigenvalue-free interval for threshold graphs
• Some notes on spectra of cographs.
• Distance eigenvalues of a cograph and their multiplicities
• Almost controllable graphs and beyond
• Extensions on spectral extrema of \(C_5/C_6\)-free graphs with given size
• Cographs: eigenvalues and Dilworth number
• Locating Eigenvalues of Symmetric Matrices - A Survey
• Characterizing and computing weight-equitable partitions of graphs
• Some spectral properties of cographs
• Laplacian spectra of cographs: a twin reduction perspective
• Multiplicity of eigenvalues of cographs
• Eigenvalue-free intervals of distance matrices of threshold and chain graphs
• Gap sets for the spectra of regular graphs with minimum spectral gap

Describes a project that uses

Uses Software

• nauty

This page was built for publication: Spectral properties of cographs and \(P_5\)-free graphs

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