✦ LIBER ✦

Bounds on the average connectivity of a graph

✍ Scribed by Peter Dankelmann; Ortrud R. Oellermann

Publisher: Elsevier Science
Year: 2003
Tongue: English
Weight: 235 KB
Volume: 129
Category: Article
ISSN: 0166-218X
DOI: 10.1016/s0166-218x(02)00572-3

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper, we consider the concept of the average connectivity of a graph, deÿned to be the average, over all pairs of vertices, of the maximum number of internally disjoint paths connecting these vertices. We establish sharp bounds for this parameter in terms of the average degree and improve one of these bounds for bipartite graphs with perfect matchings. Sharp upper bounds for planar and outerplanar graphs and cartesian products of graphs are established. Nordhaus-Gaddum-type results for this parameter and relationships between the clique number and chromatic number of a graph are also established.

📜 SIMILAR VOLUMES

Lower-bounds on the connectivities of a

Lower-bounds on the connectivities of a graph

✍ Abdol H. Esfahanian 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 372 KB 👁 1 views

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

Average Costs of a Graph Exploration: Up

Average Costs of a Graph Exploration: Upper and Lower Bounds

✍ Nicola Galli 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 168 KB

We consider the exploration of random digraphs. We give upper and lower bounds for the expected number of edges traversed during an exploration. This result implies a lower bound for the expected running time of a wide class of algorithms, e.g., breadth-first-search, depth-first-search, and algorith

A lower bound on connectivities of matro

A lower bound on connectivities of matroid base graphs

✍ Guizhen Liu 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 853 KB

The connectivity of a graph G and the corank of a matroid M are denoted by K(G) and p, respectively. X is shown that if a graph G is the base graph of a simple mat&d M, then K(G) L 2p and the lower bound of 2p izA best possible.

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

On the edge-connectivity vector of a gra

On the edge-connectivity vector of a graph

✍ Linda M. Lesniak; Raymond E. Pippert 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 202 KB