Connectivity of Cages

Hung-Lin Fu; K. C. Huang; C. A. Rodger

doi:10.1002/(SICI)1097-0118(199702)24:2<187::AID-JGT6>3.0.CO;2-M

Connectivity of Cages

Hung-Lin Fu^*, K. C. Huang, C. A. Rodger

^*Corresponding author for this work

Department of Applied Mathematics

Research output: Contribution to journal › Article › peer-review

40 Scopus citations

Abstract

A (k; g)-graph is a k-regular graph with girth g. Let f(k; g) be the smallest integer v such there exists a (k; g)-graph with v 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₁) < f(k; g₂) for all k ≥ 3 and 3 ≤ g₁ ≤ g₂. We use this to prove that (k; g)-cages are 2-connected, and if k = 3 then their connectivity is k.

Original language	English
Pages (from-to)	187-191
Number of pages	5
Journal	Journal of Graph Theory
Volume	24
Issue number	2
DOIs	https://doi.org/10.1002/(SICI)1097-0118(199702)24:2<187::AID-JGT6>3.0.CO;2-M
State	Published - 1 Jan 1997

Access to Document

10.1002/(SICI)1097-0118(199702)24:2<187::AID-JGT6>3.0.CO;2-M

Link to publication in Scopus

Fingerprint Dive into the research topics of 'Connectivity of Cages'. Together they form a unique fingerprint.

Cite this

@article{d058bea3cdde4438a5eff0e0f76398b7,

title = "Connectivity of Cages",

abstract = "A (k; g)-graph is a k-regular graph with girth g. Let f(k; g) be the smallest integer v such there exists a (k; g)-graph with v 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; g1) < f(k; g2) for all k ≥ 3 and 3 ≤ g1 ≤ g2. We use this to prove that (k; g)-cages are 2-connected, and if k = 3 then their connectivity is k.",

author = "Hung-Lin Fu and Huang, {K. C.} and Rodger, {C. A.}",

year = "1997",

month = jan,

day = "1",

doi = "10.1002/(SICI)1097-0118(199702)24:2<187::AID-JGT6>3.0.CO;2-M",

language = "English",

volume = "24",

pages = "187--191",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "2",

}

TY - JOUR

T1 - Connectivity of Cages

AU - Fu, Hung-Lin

AU - Huang, K. C.

AU - Rodger, C. A.

PY - 1997/1/1

Y1 - 1997/1/1

N2 - A (k; g)-graph is a k-regular graph with girth g. Let f(k; g) be the smallest integer v such there exists a (k; g)-graph with v 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; g1) < f(k; g2) for all k ≥ 3 and 3 ≤ g1 ≤ g2. We use this to prove that (k; g)-cages are 2-connected, and if k = 3 then their connectivity is k.

AB - A (k; g)-graph is a k-regular graph with girth g. Let f(k; g) be the smallest integer v such there exists a (k; g)-graph with v 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; g1) < f(k; g2) for all k ≥ 3 and 3 ≤ g1 ≤ g2. We use this to prove that (k; g)-cages are 2-connected, and if k = 3 then their connectivity is k.

UR - http://www.scopus.com/inward/record.url?scp=0031538595&partnerID=8YFLogxK

U2 - 10.1002/(SICI)1097-0118(199702)24:2<187::AID-JGT6>3.0.CO;2-M

DO - 10.1002/(SICI)1097-0118(199702)24:2<187::AID-JGT6>3.0.CO;2-M

M3 - Article

AN - SCOPUS:0031538595

VL - 24

SP - 187

EP - 191

JO - Journal of Graph Theory

JF - Journal of Graph Theory

SN - 0364-9024

IS - 2

ER -