Group connectivity in 3-edge-connected graphs. (English) Zbl 1256.05135
Summary: Let \(A\) be an abelian group with \(|A| \geq 4\). For integers \(k\) and \(l\) with \(k > 0\) and \(l \geq 0\), let \(\mathcal{C}(k,l)\) denote the family of 2-edge-connected graphs \(G\) such that for each edge cut \(S \subseteq E(G)\) with two or three edges, each component of \(G-S\) has at least \((|V(G)|-l)/k\) vertices.
In this paper, we show that if \(G\) is 3-edge-connected and \(G \in \mathcal{C}(6,5)\), then \(G\) is not \(A\)-connected if and only if \(G\) can be \(A\)-reduced to the Petersen graph.
In this paper, we show that if \(G\) is 3-edge-connected and \(G \in \mathcal{C}(6,5)\), then \(G\) is not \(A\)-connected if and only if \(G\) can be \(A\)-reduced to the Petersen graph.
References:
| [1] | Bondy J.A., Murty U.S.R.: Graph Theory with Applications. American Elsevier, New York (1976) · Zbl 1226.05083 |
| [2] | Broersma H.J., Xiong L.M.: A note on minimun degree conditions for supereulerian graphs. Discrete Appl. Math. 120, 35–43 (2002) · Zbl 0993.05097 · doi:10.1016/S0166-218X(01)00278-5 |
| [3] | Catlin P.A.: A reduction method to find spanning eulerian subgraphs. J. Graph Theory 12, 29–45 (1988) · Zbl 0659.05073 · doi:10.1002/jgt.3190120105 |
| [4] | Catlin P.A., Han Z.Y., Lai H.-J.: Graphs without spanning closed trails. Discrete Math. 160, 81–91 (1996) · Zbl 0859.05060 · doi:10.1016/S0012-365X(95)00149-Q |
| [5] | Catlin P.A., Li X.: Supereulerian graphs of minimum degree at least 4. J. Adv. Math. 160, 65–69 (1999) · Zbl 1054.05506 |
| [6] | Chen Z.-H.: Supereulerian graphs and the Petersen graph. J. Comb. Math. Comb. Comput. 9, 70–89 (1991) · Zbl 0751.05065 |
| [7] | Jaeger F.: Flows and generalized coloring theorems in graphs. J. Comb. Theory, B 26, 205–216 (1979) · Zbl 0422.05028 · doi:10.1016/0095-8956(79)90057-1 |
| [8] | Jaeger F., Linial N., Payan C., Tarsi N.: Group connectivity of graphsa nonhomogeneous analogue of nowhere zero flow properties. J. Comb. Theory, B 56, 165–182 (1992) · Zbl 0824.05043 · doi:10.1016/0095-8956(92)90016-Q |
| [9] | Lai H.-J.: Extending partial nowhere zero 4-flow. J. Graph Theory 30, 277–288 (1999) · Zbl 0920.05023 · doi:10.1002/(SICI)1097-0118(199904)30:4<277::AID-JGT3>3.0.CO;2-D |
| [10] | Lai H.-J.: Group connectivity of 3-edge-connected chordal graphs. Graphs Comb. 16, 165–176 (2000) · Zbl 0966.05041 · doi:10.1007/s003730050014 |
| [11] | Li D., Lai H.J., Zhan M.: Eulerian subgraphs and Hamilton-connected line graphs. Discrete Appl. Math. 145, 422–428 (2005) · Zbl 1057.05053 · doi:10.1016/j.dam.2004.04.005 |
| [12] | Li X., Li D., Lai H.J.: The Supereulerian graphs in the graph family C(l, k). Discrete Math. 309, 2937–2942 (2009) · Zbl 1200.05126 · doi:10.1016/j.disc.2008.06.038 |
| [13] | St. J.A. Nash-Williams, C.: Decompositions of finite graphs into forests. J. Lond. Math. Soc. 39, 12 (1964) · Zbl 0119.38805 |
| [14] | Tutte W.T.: A contribution on the theory of chromatic polynomial. Canad. J. Math. 6, 80–91 (1954) · Zbl 0055.17101 · doi:10.4153/CJM-1954-010-9 |
| [15] | Tutte W.T.: On the algebraic theory of graph colorings. J. Comb. Theory 1, 15–50 (1966) · Zbl 0139.41402 |
| [16] | Yao X., Li X., Lai H.: Degree conditions for group connectivity. Discerete Math. 310, 1050–1058 (2010) · Zbl 1231.05160 · doi:10.1016/j.disc.2009.10.023 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
