✦ LIBER ✦

Connectivity of k-extendable graphs with large k

✍ Scribed by Dingjun Lou; Qinglin Yu

Publisher: Elsevier Science
Year: 2004
Tongue: English
Weight: 198 KB
Volume: 136
Category: Article
ISSN: 0166-218X
DOI: 10.1016/s0166-218x(03)00198-7

No coin nor oath required. For personal study only.

✦ Synopsis

Let G be a simple connected graph on 2n vertices with perfect matching. For a given positive integer k (0

, then either G is bipartite or the connectivity of G is at least 2k. As a corollary, we show that if G is a maximal k-extendable graph on 2n vertices with n + 2 6 2k + 1, then G is Kn;n if k + 1 6 6 n and G is K2n if 2k + 1 6 6 2n -1. Moreover, if G is a minimal k-extendable graph on 2n vertices with n + 1 6 2k + 1 and k + 1 6 6 n then the minimum degree of G is k + 1. We also discuss the relationship between the k-extendable graphs and the Hamiltonian graphs.

📜 SIMILAR VOLUMES

The existence of a 2-factor in K1, n-fre

The existence of a 2-factor in K1, n-free graphs with large connectivity and large edge-connectivity

✍ R. E. L. Aldred; Yoshimi Egawa; Jun Fujisawa; Katsuhiro Ota; Akira Saito 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 130 KB 👁 1 views

In this article, we study the existence of a 2-factor in a K 1,nfree graph. Sumner [J London Math Soc 13 (1976), 351-359] proved that for n ≥ 4, an (n-1)-connected K 1,n -free graph of even order has a 1-factor.

Critically (k, k)-connected graphs

✍ Kiyoshi Ando; Yoko Usami 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 359 KB

k-connectivity in random undirected grap

k-connectivity in random undirected graphs

✍ John H Reif; Paul G Spirakis 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 591 KB

This paper concerns vertex connectivity in random graphs. We present results bounding the cardinality of the biggest k-block in random graphs of the G,~p model, for any constant value of k. Our results extend the work of Erd6s and R6nyi and Karp and Tarjan. We prove here that (~.~p, with [9 ~ tin, h

k-shredders in k-connected graphs

✍ Yoshimi Egawa 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 184 KB 👁 1 views

## Abstract For a graph __G__, a subset __S__ of __V__(__G__) is called a shredder if __G__ − __S__ consists of three or more components. We show that if __k__ ≥ 4 and __G__ is a __k__‐connected graph, then the number of shredders of cardinality __k__ of __G__ is less than 2|__V__(__G__)|/3 (we sho

Minimally (k, k)-edge-connected graphs

✍ Kamal Hennayake; Hong-Jian Lai; Deying Li; Jingzhong Mao 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 138 KB 👁 1 views

## Abstract For an integer __l__ > 1, the __l__‐edge‐connectivity of a connected graph with at least __l__ vertices is the smallest number of edges whose removal results in a graph with __l__ components. A connected graph __G__ is (__k__, __l__)‐edge‐connected if the __l__‐edge‐connectivity of __G_

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