zbMATH — the first resource for mathematics

Even subgraphs of bridgeless graphs and 2-factors of line graphs. (English) Zbl 1127.05080
Summary: By Petersen’s theorem, a bridgeless cubic multigraph has a 2-factor. Fleischner generalised this result to bridgeless multigraphs of minimum degree at least three by showing that every such multigraph has a spanning even subgraph [see H. Fleischner, Discrete Math. 101, No. 1–3, 33–37 (1992; Zbl 0764.05051)]. Our main result is that every bridgeless simple graph with minimum degree at least three has a spanning even subgraph in which every component has at least four vertices. We deduce that if \(G\) is a simple bridgeless graph with \(n\) vertices and minimum degree at least three, then its line graph has a 2-factor with at most \(\max\{1,(3n-4)/10\}\) components. This upper bound is best possible.

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Zbl 0764.05051
Full Text: DOI
[1] Chartrand, G.; Wall, C.E., On the Hamiltonian index of a graph, Studia sci. math. hungar., 8, 43-48, (1973) · Zbl 0279.05121
[2] Choudum, S.A.; Paulraj, M.S., Regular factors in \(K_{1, 3}\)-free graphs, J. graph theory, 15, 259-265, (1991) · Zbl 0756.05087
[3] Diestel, R., Graph theory, (2000), Graduate Texts in Mathematics 173 Springer Berlin · Zbl 0945.05002
[4] Egawa, Y.; Ota, K., Regular factors in \(K_{1, n}\)-free graphs, J. graph theory, 15, 337-344, (1991) · Zbl 0756.05088
[5] Faudree, R.J.; Favaron, O.; Flandrin, E.; Li, H.; Liu, Z., On 2-factors in claw-free graphs, Discrete math., 206, 131-137, (1999) · Zbl 0981.05084
[6] Fleischner, H., Spanning eulerian subgraphs, the splitting lemma, and Petersen’s theorem, Discrete math., 101, 33-37, (1992) · Zbl 0764.05051
[7] Fujisawa, J.; Xiong, L.; Yoshimoto, K.; Zhang, S., The upper bound of the number of cycles in a 2-factor of a line graph, J. graph theory, 55, 72-82, (2007) · Zbl 1118.05049
[8] Gould, R.; Hynds, E., A note on cycles in 2-factors of line graphs, Bull. of ICA., 26, 46-48, (1999) · Zbl 0922.05046
[9] Gould, R.J.; Jacobson, M.S., Two-factors with few cycles in claw-free graphs, Discrete math., 231, 191-197, (2001) · Zbl 0979.05084
[10] B. Jackson, K. Yoshimoto, Spanning even subgraphs of 3-edge-connected graphs, preprint. · Zbl 1180.05057
[11] Mader, W., A reduction method for edge-connectivity in graphs, Ann. discrete math., 3, 145-164, (1978) · Zbl 0389.05042
[12] Nishimura, T., Regular factors of line graphs, Discrete math., 85, 215-219, (1990) · Zbl 0714.05056
[13] Petersen, J., Die theorie der regulären graphen, Acta math., 15, 193-220, (1891) · JFM 23.0115.03
[14] Ryjácěk, Z., On a closure concept in claw-free graphs, J. combin. theory ser. B, 70, 217-224, (1997) · Zbl 0872.05032
[15] Ryjácěk, Z.; Saito, A.; Schelp, R.H., Closure, 2-factor, and cycle coverings in claw-free graphs, J. graph theory, 32, 109-117, (1999) · Zbl 0932.05045
[16] K. Yoshimoto, On the number of components in a 2-factor of a claw-free graph, preprint. · Zbl 1129.05037
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.