×

zbMATH — the first resource for mathematics

Spanning cycles in regular matroids without small cocircuits. (English) Zbl 1248.05030
Summary: A cycle of a matroid is a disjoint union of circuits. A cycle \(C\) of a matroid \(M\) is spanning if the rank of \(C\) equals the rank of \(M\). Settling an open problem of D. Bauer [Congr. Numerantium 49, 11–18 (1985; Zbl 0621.05021)], P. A. Catlin [J. Graph Theory 12, No. 1, 29–44 (1988; Zbl 0659.05073)] showed that if \(G\) is a 2-connected graph on \(n>16\) vertices, and if \(\delta(G)>\frac {n}{5}-1\), then \(G\) has a spanning cycle. Catlin also showed that the lower bound of the minimum degree in this result is best possible. In this paper, we prove that for a connected simple regular matroid \(M\), if for any cocircuit \(D\), \(|D|\geq \) max\(\{\frac {r(M)-4}{5},6\}\), then \(M\) has a spanning cycle.

MSC:
05B35 Combinatorial aspects of matroids and geometric lattices
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bauer, D., A note on degree conditions for Hamiltonian cycles in line graphs, Congr. numer., 49, 11-18, (1985)
[2] Boesch, F.T.; Suffel, C.; Tindell, R., The spanning subgraphs of Eulerian graphs, J. graph theory, 1, 79-84, (1977) · Zbl 0363.05042
[3] Bondy, J.A.; Murty, U.S.R., Graph theory, (2008), Springer New York · Zbl 1134.05001
[4] Catlin, P.A., A reduction method to find spanning Eulerian subgraphs, J. graph theory, 12, 29-44, (1988) · Zbl 0659.05073
[5] Catlin, P.A., Supereulerian graphs, a survey, J. graph theory, 16, 177-196, (1992) · Zbl 0771.05059
[6] Catlin, P.A.; Grossman, J.W.; Hobbs, A.M.; Lai, H.-J., Fractional arboricity, strength and principal partitions in graphs and matroids, Discrete appl. math., 40, 285-302, (1992) · Zbl 0773.05033
[7] Catlin, P.A.; Han, Z.Y.; Lai, H.-J., Graphs without spanning closed trails, J. discrete math., 160, 81-91, (1996) · Zbl 0859.05060
[8] Chen, Z.H.; Lai, H.-J., Reduction techniques for super-Eulerian graphs and related topics-a survey, (), 53-69
[9] Edmonds, J., Lehman’s switching game and a theorem of Tutte and Nash-Williams, J. res. nat. bur. stand sect. B, 69B, 73-77, (1965) · Zbl 0192.09102
[10] Erdös, P., Graph theory and probability, Can. J. math., 11, 34-38, (1959) · Zbl 0084.39602
[11] Hochstättler, Winfried; Jackson, Bill, Large circuits in binary matroids of large cogirth I, J. combin. theory, ser. B, 74, 35-52, (1998) · Zbl 0904.05023
[12] Jaeger, F., A note on Subeulerian graphs, J. graph theory, 3, 91-93, (1979)
[13] Kronk, H.V.; Mitchem, J., Critical point arboritic graphs, J. lond. math. soc., 9, 459-466, (1974/75) · Zbl 0298.05132
[14] Lai, H.-J.; Liu, B.; Liu, Y.; Shao, Y., Spanning cycles in regular matroids without \(M^\ast(K_5)\) minors, European J. combin., 29, 1, 298-310, (2008) · Zbl 1126.05031
[15] Nash-Williams, C.St.J.A., Edge-disjoint spanning trees of finite graphs, J. lond. math. soc., 36, 445-450, (1961) · Zbl 0102.38805
[16] Oxley, J.G., Matroid theory, (1992), Oxford University Press New York · Zbl 0784.05002
[17] Pulleyblank, W.R., A note on graphs spanned by Eulerian graphs, J. graph theory, 3, 309-310, (1979) · Zbl 0414.05040
[18] Seymour, P.D., Decomposition of regular matroids, J. combin. theory, ser. B, 28, 305-359, (1980) · Zbl 0443.05027
[19] Seymour, P.D., Matroids and multicommodity flows, European J. combin. theory ser. B, 2, 257-290, (1981) · Zbl 0479.05023
[20] Tutte, W.T., On the problem of decomposing a graph into \(n\) connected factors, J. lond. math. soc., 36, 221-230, (1961) · Zbl 0096.38001
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.