✦ LIBER ✦

Tree-width, clique-minors, and eigenvalues

✍ Scribed by Yuan Hong

Publisher: Elsevier Science
Year: 2004
Tongue: English
Weight: 187 KB
Volume: 274
Category: Article
ISSN: 0012-365X
DOI: 10.1016/s0012-365x(03)00199-7

No coin nor oath required. For personal study only.

✦ Synopsis

Let G be a simple graph with n vertices and tw(G) be the tree-width of G. Let (G) be the spectral radius of G and (G) be the smallest eigenvalue of G. The join G∇H of disjoint graphs of G and H is the graph obtained from G + H by joining each vertex of G to each vertex of H . In this paper, several results which are concerned with tree-width, clique-minors, and eigenvalues of graphs are given. In particular, we have

(1) If G is K5 minor-free graph, then

where equality holds if and only if G is isomorphic to K3∇(n -3)K1.

(2) If G is K5 minor-free graph with n ¿ 5 vertices, then

where equality holds if and only if G is isomorphic to K3;n-3.

📜 SIMILAR VOLUMES

Surfaces, Tree-Width, Clique-Minors, and

Surfaces, Tree-Width, Clique-Minors, and Partitions

✍ Guoli Ding; Bogdan Oporowski; Daniel P. Sanders; Dirk Vertigan 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 214 KB

In 1971, Chartrand, Geller, and Hedetniemi conjectured that the edge set of a planar graph may be partitioned into two subsets, each of which induces an outerplanar graph. Some partial results towards this conjecture are presented. One such result, in which a planar graph may be thus edge partitione

Local Tree-Width, Excluded Minors, and A

Local Tree-Width, Excluded Minors, and Approximation Algorithms

✍ Martin Grohe 📂 Article 📅 2003 🏛 Springer-Verlag 🌐 English ⚖ 276 KB

Graph minors. II. Algorithmic aspects of

Graph minors. II. Algorithmic aspects of tree-width

✍ Neil Robertson; P.D Seymour 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 734 KB

Independence number and clique minors

✍ Ken-ichi Kawarabayashi; Zi-Xia Song 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 122 KB

## Abstract The Hadwiger number ${h}({G})$ of a graph __G__ is the maximum integer __t__ such that ${K}\_{t}$ is a minor of __G__. Since $\chi({G})\cdot\alpha({G})\geq |{G}|$, Hadwiger's conjecture implies that ${h}({G})\cdot \alpha({G})\geq |{G}|$, where $\alpha({G})$ and $|{G}|$ denote the indepe

Multiplicities of Eigenvalues and Tree-W

Multiplicities of Eigenvalues and Tree-Width of Graphs

✍ Yves Colin de Verdière 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 567 KB

Using multiplicities of eigenvalues of elliptic self-adjoint differential operators on graphs and transversality, we construct some new invariants of graphs which are related to tree-width.

Ka,k Minors in Graphs of Bounded Tree-Wi

Ka,k Minors in Graphs of Bounded Tree-Width

✍ Thomas Böhme; John Maharry; Bojan Mohar 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 175 KB

It is shown that for any positive integers k and w there exists a constant N ¼ N ðk; wÞ such that every 7-connected graph of tree-width less than w and of order at least N contains K 3;k as a minor. Similar result is proved for K a;k minors where a is an arbitrary fixed integer and the required conn