✦ LIBER ✦

A spectral lower bound for the treewidth of a graph and its consequences

✍ Scribed by L.Sunil Chandran; C.R. Subramanian

Publisher: Elsevier Science
Year: 2003
Tongue: English
Weight: 95 KB
Volume: 87
Category: Article
ISSN: 0020-0190
DOI: 10.1016/s0020-0190(03)00286-2

No coin nor oath required. For personal study only.

✦ Synopsis

We give a lower bound for the treewidth of a graph in terms of the second smallest eigenvalue of its Laplacian matrix. We use this lower bound to show that the treewidth of a d-dimensional hypercube is at least 3

We generalize this result to Hamming graphs. We also observe that every graph G on n vertices, with maximum degree ∆

(1) contains an induced cycle (chordless cycle) of length at least 1 + log ∆ (µn/8) (provided G is not acyclic), (2) has a clique minor K h for some h = ((nµ 2 /(∆ + 2µ) 2 ) 1/3 ), where µ is the second smallest eigenvalue of the Laplacian matrix of G.

📜 SIMILAR VOLUMES

A lower bound for the circumference of a

A lower bound for the circumference of a graph

✍ Nathan Linial 📂 Article 📅 1976 🏛 Elsevier Science 🌐 English ⚖ 423 KB

Lrzt G = (V, 0 be a ttlock :.>f order n, different from Kn. Let ~FI = min {d(x) + d(y): n then G contains a cycle of length at least m. 1. Introductlion and notatio e discuss only finite undirected graphs withsLc loops and multiple edges. We p:rosye the main theorem d show how Qre's th -orem [ 3.1 o

A lower bound for the independence numbe

A lower bound for the independence number of a planar graph

✍ Michael O Albertson 📂 Article 📅 1976 🏛 Elsevier Science 🌐 English ⚖ 403 KB

A lower bound for the spectral radius of

A lower bound for the spectral radius of a digraph

✍ E. Gudiño; J. Rada 📂 Article 📅 2010 🏛 Elsevier Science 🌐 English ⚖ 161 KB

Spectral bounds for the betweenness of a

Spectral bounds for the betweenness of a graph

✍ F. Comellas; S. Gago 📂 Article 📅 2007 🏛 Elsevier Science 🌐 English ⚖ 127 KB

Lower bounds for the spectral radius of

Lower bounds for the spectral radius of a matrix

✍ Bill G. Horne 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 444 KB

We develop lower bounds for the spectral radius of symmetric, skew-symmetric, and arbitrary real matrices, Our approach utilizes the well-known Leverrier-Faddeev algorithm for calculating the coefficients of the characteristic polynomial of a matrix in conjunction with a theorem by Lucas which state

The spectral radii of a graph and its li

The spectral radii of a graph and its line graph

✍ Lingsheng Shi 📂 Article 📅 2007 🏛 Elsevier Science 🌐 English ⚖ 150 KB

The spectral radius of a (directed) graph is the largest eigenvalue of adjacency matrix of the (directed) graph. We give the relation on the characteristic polynomials of a directed graph and its line graph, and obtain sharp bounds on the spectral radius of directed graphs. We also give the relation