×

zbMATH — the first resource for mathematics

Spanning cycles in regular matroids without \(M^{*}(K_{5})\) minors. (English) Zbl 1126.05031
Summary: Catlin and Jaeger proved that the cycle matroid of a 4-edge-connected graph has a spanning cycle. This result can not be generalized to regular matroids as there exist infinitely many connected cographic matroids, each of which contains a \(M^{*}(K_{5})\)-minor and has arbitrarily large cogirth, that do not have spanning cycles. In this paper, we proved that if a connected regular matroid without a \(M^{*}(K_{5})\)-minor has cogirth at least 4, then it has a spanning cycle.

MSC:
05B35 Combinatorial aspects of matroids and geometric lattices
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Appel, K.; Haken, W., Every planar map is four colorable, part I: discharging, Illinois J. math., 21, 429-490, (1977) · Zbl 0387.05009
[2] Appel, K.; Haken, W.; Koch, J., Every planar map is four colorable, part II: reducibility, Illinois J. math., 21, 491-567, (1977) · Zbl 0387.05010
[3] Boesch, F.T.; Suffel, C.; Tindell, R., The spanning subgraphs of Eulerian graphs, J. graph theory, 1, 79-84, (1977) · Zbl 0363.05042
[4] Bollobás, B., Graph theory, (1979), Springer-Verlag New York · Zbl 0418.05049
[5] Bondy, J.A.; Murty, U.S.R., Graph theory with applications, (1976), American Elsevier New York · Zbl 1134.05001
[6] Catlin, P.A., A reduction method to find spanning Eulerian subgraphs, J. graph theory, 12, 29-44, (1988) · Zbl 0659.05073
[7] P.A. Catlin, H.-J. Lai, Y. Shao, Edge-connectivity and edge-disjoint spanning trees (submitted for publication)
[8] Catlin, P.A.; Lai, H.-J., Spanning trails joining two given edges, (), 207-222 · Zbl 0841.05067
[9] Catlin, P.A.; Han, Z.Y.; Lai, H.-J., Graphs without spanning closed trails, Discrete math., 160, 81-91, (1996) · Zbl 0859.05060
[10] Jaeger, F., A note on Subeulerian graphs, J. graph theory, 3, 91-93, (1979)
[11] Nash-Williams, C.St.J.A., Edge-disjoint spanning trees of finite graphs, J. London math. soc., 36, 445-450, (1961) · Zbl 0102.38805
[12] Nash-Williams, C.St.J.A., Decomposition of finite graphs into forests, J. London math. soc., 39, 12, (1964) · Zbl 0119.38805
[13] Oxley, J.G., Matroid theory, (1992), Oxford University Press New York · Zbl 0784.05002
[14] Pulleyblank, W.R., A note on graphs spanned by Eulerian graphs, J. graph theory, 3, 309-310, (1979) · Zbl 0414.05040
[15] Robertson, N.; Sanders, D.; Seymour, P.; Thomas, R., The four-color theorem, J. combin. theory ser. B, 70, 2-44, (1997) · Zbl 0883.05056
[16] Seymour, P.D., Decomposition of regular matroids, J. combin. theory ser. B, 28, 305-359, (1980) · Zbl 0443.05027
[17] Seymour, P.D., Matroids and multicommodity flows, European J. combin. theory ser. B., 2, 257-290, (1981) · Zbl 0479.05023
[18] Tutte, W.T., A homotopy theorem for matroids, I, II, Trans. amer. math. soc., 88, 144-174, (1958) · Zbl 0081.17301
[19] Tutte, W.T., On the problem of decomposing a graph into \(n\) connected factors, J. London math. soc., 36, 80-91, (1961) · Zbl 0096.38001
[20] Veblen, O., An application of modular equations in analysis situs, Ann. of math., 14, 86-94, (1912-1913) · JFM 43.0574.01
[21] Wagner, K., Über eine eigneschaft der ebenen komplexe, Math. ann., 144, 570-590, (1937) · JFM 63.0550.01
[22] Welsh, D.J.A., Matroid theory, (1976), Academic Press London · Zbl 0343.05002
[23] Welsh, D.J.A., Euler and bipartite matroids, J. combin. theory, 6, 313-316, (1969) · Zbl 0167.01704
[24] Zhan, S.M., Hamiltonian connectedness of line graphs, Ars combin., 22, 89-95, (1986) · Zbl 0611.05038
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.