✦ LIBER ✦

Connectivity and separating sets of cages

✍ Scribed by Jiang, Tao; Mubayi, Dhruv

Publisher: John Wiley and Sons
Year: 1998
Tongue: English
Weight: 245 KB
Volume: 29
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199809)29:1<35::aid-jgt4>3.0.co;2-f

No coin nor oath required. For personal study only.

✦ Synopsis

A (k; g)-cage is a graph of minimum order among k-regular graphs with girth g. We show that for every cutset S of a (k; g)-cage G, the induced subgraph G[S] has diameter at least g/2 , with equality only when distance g/2 occurs for at least two pairs of vertices in G[S]. This structural property is used to prove that every (k; g)-cage with k ≥ 3 is 3-connected. This result supports the conjecture of Fu, Huang, and Rodger that every

is connected. We prove that every (k; g)-cage contains a nonseparating g-cycle.

For even g, we prove that every g-cycle in a (k; g)-cage is nonseparating.

📜 SIMILAR VOLUMES

Connectivity of cages

✍ Fu, H. L.; Huang, K. C.; Rodger, C. A. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 85 KB

A (k; g)-graph is a k-regular graph with girth g. Let f (k; g) be the smallest integer ν such there exists a (k; g)-graph with ν vertices. A (k; g)-cage is a (k; g)-graph with f (k; g) vertices. In this paper we prove that the cages are monotonic in that f (k; g 1 ) < f(k; g 2 ) for all k ≥ 3 and 3

On the connectivity of semiregular cages

✍ C. Balbuena; D. González-Moreno; X. Marcote 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 186 KB

## Abstract An ({__r__, __r__ + 1}; __g__)‐cage is a graph with degree set {__r__, __r__ + 1}, girth __g__, and with the smallest possible order; every such graph is called a semiregular cage. In this article, semiregular cages are shown to be maximally edge‐connected and 2‐connected. As a conseque

Minimal Completely Separating Systems of

Minimal Completely Separating Systems of k-Sets

✍ André Kündgen; Dhruv Mubayi; Prasad Tetali 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 117 KB

Let n and k be fixed positive integers. A collection C of k-sets of [n] is a completely separating system if, for all distinct i, j # [n], there is an S # C for which i # S and j Â S. Let R(n, k) denote the minimum size of such a C. Our results include showing that if n k is a sequence with k< 0, th

Connectivity properties of dimension lev

Connectivity properties of dimension level sets

✍ Jack H. Lutz; Klaus Weihrauch 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 137 KB

## Abstract This paper initiates the study of sets in Euclidean spaces ℝ^__n__^ (__n__ ≥ 2) that are defined in terms of the dimensions of their elements. Specifically, given an interval __I__ ⊆ [0, __n__ ], we are interested in the connectivity properties of the set DIM^__I__^ , consisting of all

Rainbow connection number and connected

Rainbow connection number and connected dominating sets

✍ L. Sunil Chandran; Anita Das; Deepak Rajendraprasad; Nithin M. Varma 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 167 KB

## Abstract The __rainbow connection number__ of a connected graph is the minimum number of colors needed to color its edges, so that every pair of its vertices is connected by at least one path in which no two edges are colored the same. In this article we show that for every connected graph on __

A Weak Form of Connected Sets

✍ Takashi Noiri 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 304 KB