On superconnectivity of (4,g)-cages with even girth | NOVA. The University of Newcastle's Digital Repository

Home

Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.13/928266

Title: On superconnectivity of (4,g)-cages with even girth
Author/Creator: Lin, Yuqing; Lu, Hongliang; Wu, Yunjian; Yu, Qinglin
Institution: The University of Newcastle. Faculty of Engineering & Built Environment, School of Electrical Engineering and Computer Science
Description: A (k,g)-cage is a k-regular graph with girth g that has the fewest number of vertices. It has been conjectured (Fu et al., J Graph Theory 24 (1997), 187–191) that all (k,g)-cages are k-connected for k ≥ 3. A connected graph G is said to be superconnected if every minimum cut-set S is the neighborhood of a vertex of minimum degree. Moreover, if G − S has precisely two components, then G is called tightly superconnected. It was shown (Xu et al., Ars Combin 64 (2002), 181–192) that every (4,g)-cage is 4-connected. In this article, we prove that every (4,g)-cage is tightly superconnected when g is even and g ≥ 12.
Relation: Networks Vol. 56, Issue 2, p. 143-148
Publisher Link: http://dx.doi.org/10.1002/net.20355
Date: 2010
Publisher: John Wiley
Keyword(s): cage; girth; superconnected; tightly superconnected
Resource Type: journal article
Identifier: http://hdl.handle.net/1959.13/928266
Identifier: ISSN:0028-3045

10 Visitors

12 Hits

NOVA. The University of Newcastle's Digital Repository