𝔖 Bobbio Scriptorium
✦   LIBER   ✦

All (k;g)-cages are k-edge-connected

✍ Scribed by Yuqing Lin; Mirka Miller; Chris Rodger

Publisher
John Wiley and Sons
Year
2005
Tongue
English
Weight
116 KB
Volume
48
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A (k;g)‐cage is a k‐regular graph with girth g and with the least possible number of vertices. In this paper, we prove that (k;g)‐cages are k‐edge‐connected if g is even. Earlier, Wang, Xu, and Wang proved that (k;g)‐cages are k‐edge‐connected if g is odd. Combining our results, we conclude that the (k;g)‐cages are k‐edge‐connected. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 219–227, 2005

📜 SIMILAR VOLUMES

All (k;g)-cages are edge-superconnected
All (k;g)-cages are edge-superconnected
✍ Yuqing Lin; Mirka Miller; C. Balbuena; X. Marcote 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 200 KB

## Abstract A (__k__;__g__)‐cage is a __k__‐regular graph with girth __g__ and with the least possible number of vertices. In this article we prove that (__k__;__g__)‐cages are edge‐superconnected if __g__ is even. Earlier, Marcote and Balbuena proved that (__k__;__g__)‐cages are edge‐superconnecte

Minimally (k, k)-edge-connected graphs
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_

k-shredders in k-connected graphs
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

Connected, locally 2-connected, K1,3-fre
Connected, locally 2-connected, K1,3-free graphs are panconnected
✍ S. V. Kanetkar; P. R. Rao 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 288 KB 👁 1 views

## Abstract A graph __G__ is locally __n__‐connected, __n__ ≥ 1, if the subgraph induced by the neighborhood of each vertex is __n__‐connected. We prove that every connected, locally 2‐connected graph containing no induced subgraph isomorphic to __K__~1,3~ is panconnected.

The number of vertices of degree k in a
The number of vertices of degree k in a minimally k-edge-connected digraph
✍ Yuan Xu-dong; Kang Liying; Cai Mao-cheng 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 298 KB 👁 2 views

Let k be a positive integer, and D = (V (D), E(D)) be a minimally k-edge-connected simple digraph. We denote the outdegree and indegree of x ∈ V (D) by δ D (x) and ρ D (x), respectively. Let u + (D) denote the number of vertices W. Mader asked the following question in [Mader, in Paul Erdös is Eigh