Spectral properties of cographs and P₅-free graphs

DOI10.1080/03081087.2018.1466865zbMATH Open1415.05105arXiv1602.02069OpenAlexW2801741760MaRDI QIDQ4967261FDOQ4967261

Authors: E. Ghorbani 

Publication date: 3 July 2019

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

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)$.

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

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

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)

Cites Work

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

Cited In (16)

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

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)