𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the k-diameter of k-regular k-connected graphs

✍ Scribed by D. Frank Hsu; Tomasz Łuczak

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
391 KB
Volume
133
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

We study the k-diameter of k-regular k-connected graphs. Among other results, we show that every k-regular k-connected graph on n vertices has k-diameter at most n/2 and this upper bound cannot be improved when n = 4k -6 + i(2k -4). In particular, the maximal 3-diameter of 3-regular graphs with 2n vertices is equal to n.

📜 SIMILAR VOLUMES

Circuits through prescribed vertices in
Circuits through prescribed vertices in k-connected k-regular graphs
✍ Roland Häggkvist; Wolfgang Mader 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 178 KB 👁 1 views

## Abstract We show that every set of $k+\lfloor{1\over 3}\sqrt{k}\rfloor$ vertices in a __k__‐connected __k__‐regular graph belongs to some circuit. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 145–163, 2002

Connected [k, k + 1]-factors of graphs
Connected [k, k + 1]-factors of graphs
✍ Mao-cheng Cai 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 541 KB

Let k be an odd integer /> 3, and G be a connected graph of odd order n with n/>4k -3, and minimum degree at least k. In this paper it is proved that if for each pair of nonadjacent vertices u, v in G max{dG(u), d~(v)} >~n/2, then G has an almost k--factor F + and a matching M such that F-and M are

On k-critical, n-connected graphs
On k-critical, n-connected graphs
✍ Stephen Maurer; Peter J. Slater 📂 Article 📅 1977 🏛 Elsevier Science 🌐 English ⚖ 718 KB

A graph G which iit n-connected (but not (I! I)-connected) is defined ro be k-xitical if for every S 6; V(G), where f S i d k. the connectivity of G -I S is h -/S ia We will say that G is an (n\*,k\*) graph if G is n-conneckxt (b:lt nat (n t Itconnected) and k-crirical (hut not (k c l)criticaf). Thi

The k-Critical 2k-Connected Graphs for k
The k-Critical 2k-Connected Graphs for k∈{3, 4}
✍ Matthias Kriesell 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 180 KB

A noncomplete graph G is called an (n, k)-graph if it is n-connected and G&X is not (n&|X | +1)-connected for any X V(G) with |X | k. Mader conjectured that for k 3 the graph K 2k+2 -(1-factor) is the unique (2k, k)-graph. We settle this conjecture for k 4.