Laplacian Spectrum of Weakly Quasi-threshold Graphs |
| |
Authors: | R?B?Bapat Email author" target="_blank">A?K?LalEmail author Sukanta?Pati |
| |
Institution: | (1) Stat-Math Unit, Indian Statistical Institute Delhi, 7-SJSS Marg, New Delhi, 110 016, India;(2) Indian Institute of Technology Kanpur, Kanpur, 208 016, India;(3) Department of Mathematics, Indian Institute of Technology, Guwahati, India |
| |
Abstract: | In this paper we study the class of weakly quasi-threshold graphs that are obtained from a vertex by recursively applying
the operations (i) adding a new isolated vertex, (ii) adding a new vertex and making it adjacent to all old vertices, (iii)
disjoint union of two old graphs, and (iv) adding a new vertex and making it adjacent to all neighbours of an old vertex.
This class contains the class of quasi-threshold graphs. We show that weakly quasi-threshold graphs are precisely the comparability
graphs of a forest consisting of rooted trees with each vertex of a tree being replaced by an independent set. We also supply
a quadratic time algorithm in the the size of the vertex set for recognizing such a graph. We completely determine the Laplacian
spectrum of weakly quasi-threshold graphs. It turns out that weakly quasi-threshold graphs are Laplacian integral. As a corollary
we obtain a closed formula for the number of spanning trees in such graphs. A conjecture of Grone and Merris asserts that
the spectrum of the Laplacian of any graph is majorized by the conjugate of the degree sequence of the graph. We show that
the conjecture holds for cographs.
Prof. Bapat and Prof. Pati take this opportunity to thank the Indian Institute of Technology Kanpur for the invitation. The
authors also wish to thank the Department of Science and Technology, New Delhi for the project grant. |
| |
Keywords: | Mathematical Subject Classification (2000)" target="_blank">Mathematical Subject Classification (2000) Primary: 05C50 05C07 Secondary: 15A18 |
本文献已被 SpringerLink 等数据库收录! |
|