✦ LIBER ✦

Computing tight upper bounds on the algebraic connectivity of certain graphs

✍ Scribed by Oscar Rojo

Publisher: Elsevier Science
Year: 2009
Tongue: English
Weight: 176 KB
Volume: 430
Category: Article
ISSN: 0024-3795
DOI: 10.1016/j.laa.2008.08.018

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Tight bounds on the algebraic connectivi

Tight bounds on the algebraic connectivity of Bethe trees

✍ Oscar Rojo; Luis Medina 📂 Article 📅 2006 🏛 Elsevier Science 🌐 English ⚖ 190 KB

An upper bound for orders of certain (k,

An upper bound for orders of certain (k, k))-connected graphs

✍ Kiyoshi Ando 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 275 KB

A fragment of a connected graph G is a subset A of V(C) consisting of components of G-S such that V(G)-S-A #0 where S is a minimum cut of G. A graph G is said to be (k, I;)- We prove the following result. Let k and k be integers with 1 <i < k, and let G be a critically (k, k)-connected graph. If no

Tight bounds on the chromatic sum of a c

Tight bounds on the chromatic sum of a connected graph

✍ Carsten Thomassen; Paul Erdös; Yousef Alavi; Paresh J. Malde; Allen J. Schwenk 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 236 KB 👁 1 views

A lower bound for algebraic connectivity

A lower bound for algebraic connectivity based on the connection-graph-stability method

✍ Ali Ajdari Rad; Mahdi Jalili; Martin Hasler 📂 Article 📅 2011 🏛 Elsevier Science 🌐 English ⚖ 323 KB

An upper bound for the radius of a 3-con

An upper bound for the radius of a 3-connected graph

✍ Jochen Harant 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 286 KB

For a 3-connected graph with radius r containing n vertices, in [1] r < n/4 + O(log n) was proved and r < n/4 + const was conjectured. Here we prove r < n/4 + 8. Let G be a simple 3-connected finite graph on n vertices with vertex set V(G) and edge set E(G). For X, YE V(G) we denote by d(X, Y) the

New upper bounds on the decomposability

New upper bounds on the decomposability of planar graphs

✍ Fedor V. Fomin; Dimitrios M. Thilikos 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 335 KB 👁 1 views

## Abstract It is known that a planar graph on __n__ vertices has branch‐width/tree‐width bounded by $\alpha \sqrt {n}$. In many algorithmic applications, it is useful to have a small bound on the constant α. We give a proof of the best, so far, upper bound for the constant α. In particular, for th