Abstract
A cyclic edge-cut of a connected graph \(G\) is an edge set, the removal of which separates two cycles. If \(G\) has a cyclic edge-cut, then it is called cyclically separable. For a cyclically separable graph \(G\), the cyclic edge connectivity of a graph \(G\), denoted by \(\lambda _c(G)\), is the minimum cardinality over all cyclic edge cuts. Let \(X\) be a non-empty proper subset of \(V(G)\). If \([X,\overline{X}]=\{xy\in E(G)\ |\ x\in X, y\in \overline{X}\}\) is a minimum cyclic edge cut of \(G\), then \(X\) is called a \(\lambda _c\) -fragment of \(G\). A \(\lambda _c\)-fragment with minimum cardinality is called a \(\lambda _c\) -atom. Let \(G\) be a \(k (k\ge 3)\)-regular cyclically separable graph with \(\lambda _c(G)<g(k-2)\), where \(g\) is the girth of \(G\). A combination of the results of Nedela and Skoviera (Math Slovaca 45:481–499, 1995) and Xu and Liu (Australas J Combin 30:41–49, 2004) gives that if \(k\ne 5\) then any two distinct \(\lambda _c\)-atoms of \(G\) are disjoint. The remaining case of \(k=5\) is considered in this paper, and a new proof for Nedela and Škoviera’s result is also given. As a result, we obtain the following result. If \(X\) and \(X'\) are two distinct \(\lambda _c\)-atoms of \(G\) such that \(X\cap X'\ne \emptyset \), then \((k,g)=(5,3)\) and \(G[X]\cong K_4\). As corollaries, several previous results are easily obtained.
Similar content being viewed by others
References
Bollobás B (1978) Extremal graph theory. Academic Press, London
Esfahanian A, Hakimi S (1988) On computing a conditional edge-connectivity of a graph. Inf Process Lett 27:195–199
Godsil C, Royle G (2001) Algebraic graph theory. Springer, New York
Holton DA, Lou D, Plummer MD (1991) On the 2-extendability of planar graphs. Discret Math 96:81–99
Kardoš F, Šrekovski R (2008) Cyclic edge-cuts in fullerene graphs. J Math Chem 44:121–132
Latifi S, Hegde M, Naraghi-Pour M (1994) Conditional connectivity measures for large multiprocessor systems. IEEE Trans Comput 43:218–222
Lou D, Holton DA (1993) Lower bound of cyclic edge connectivity for \(n\)-extendability of regular graphs. Discret Math 112:139–150
Lovász L (1965) On graphs not containing independent circuits. Mat Lapole 16:289–299 (in Hungarian)
Lovász L (1979) Combinatorial problems and exercises. North-Holland, Amsterdam
Máčajová E, Šoviera M (2011) Infinitely many Hypohamiltonian cubic graphs of girth 7. Gr Comb 27:231–241
Mader W (1971) Minimale \(n\)-fach kantenzusammenhagenden Graphen. Math Ann 191:21–28
Nedela R, Škoviera M (1995) Atoms of cyclic connectivity in cubic graphs. Math Slovaca 45:481–499
Plummer MD (1972) On the cyclic connectivity of planar graphs. Lect Notes Math 303:235–242
Tait PG (1880) Remarks on the colouring of maps. Proc R Soc Edinb 10:501–503
Tian Y, Meng J (2009) \(\lambda _c\)-Optimal half vertex transitive graphs with regularity \(k\). Inf Process Lett 109:683–686
Tutte W (1966) Connectivity in graphs. University of Toronto Press, Toronto
Wang B, Zhang Z (2009) On the cyclic edge-connectivity of transitive graphs. Discret Math 309:4555–4563
Watkins ME (1970) Connectivity of transitive graphs. J Comb Theory 8:23–29
Xu J-M (2000) On conditional edge-connectivity of graphs. Acta Math Appl Sin B 16:414–419
Xu J-M, Xu K-L (2002) On restricted edge-connectivity of graphs. Discret Math 243:291–298
Xu J-M, Liu Q (2004) 2-Restricted edge-connectivity of vertex-transitive graphs. Australas J Comb 30:41–49
Zhang CQ (1997) Integer flows and cycle covers of graphs. Marcel Dekker, New York
Zhang Z, Wang B (2011) Super cyclically edge-connected transitive graphs. J Comb Optim 22:549–562
Acknowledgments
The author is grateful to Professor Nedela and Škoviera for their kindly help. This work was supported by the National Natural Science Foundation of China (11271012).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Zhou, JX. Atoms of cyclic edge connectivity in regular graphs. J Comb Optim 31, 382–395 (2016). https://doi.org/10.1007/s10878-014-9759-4
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-014-9759-4