Properties of Hamilton cycles of circuit graphs of matroids

Abstract

Let G be a circuit graph of a connected matroid. P. Li and G. Liu [Comput. Math. Appl., 2008, 55: 654-659] proved that G has a Hamilton cycle including e and another Hamilton cycle excluding e for any edge eof Gif Ghas at least four vertices. This paper proves that G has a Hamilton cycle including e and excluding e^' for any two edges e and e^'of G if G has at least five vertices. This result is best possible in some sense. An open problem is proposed in the end of this paper.

Keywords

Matroid / circuit graph of matroid / Hamilton cycle

References

[1] Alspach B, Liu G. Paths and cycles in matroid base graphs. Graphs Combin, 1989, 5: 207-211

[2] Bondy J A, Ingleton A W. Pancyclic graphs II. J Combin Theory Ser B, 1976, 20: 41-46

[3] Bondy J A, Murty U S R. Graph Theory with Applications. New York: American Elsevier Publishing Co, Inc, 1976

[4] Broersma H J, Li X. The connectivity of the basis graph of a branching greedoid. J Graph Theory, 1992, 16: 233-237

[5] Harary F, Plantholt M J. Classification of interpolation theorems for spanning trees and other families of spanning subgraphs. J Graph Theory, 1989, 13(6): 703-712

[6] Holzman C A, Harary F. On the tree graph of a matroid. Adv Math, 1972, 22: 187-193

[7] Li L, Bian Q, Liu G. The base incidence graph of a matroid. J Shandong University, 2005, 40(2): 24-40

[8] Li L, Liu G. The connectivities of the adjacency leaf exchange forest graphs. J Shandong University, 2004, 39(6): 49-51

[9] Li P, Liu G. Cycles in circuit graphs of matroids. Graphs Combin, 2007, 23: 425-431

[10] Li P, Liu G. The edge connectivity of circuit graphs of matroid. In: ICCS 2007, Part III. LNCS, Vol 4489. 2007, 313-319

[11] Li P, Liu G. Hamilton cycles in circuit graphs of matroids. Comput Math Appl, 2008, 55: 654-659

[12] Liu G. A lower bound on connectivities of matroid base graphs. Discrete Math, 1988, 64: 55-66

[13] Liu G. The proof of a conjecture on matroid basis graphs. Sci China Ser A, 1990, (6): 593-599

[14] Liu G, Li P. Paths in circuit graphs of matroids. Theoret Comput Sci, 2008, 396(1-3): 258-263

[15] Liu G, Zhang L. Forest graphs of graphs. Chinese J Eng Math, 2005, 22(6): 1100-1104

[16] Maurer S B. Matroid basis graphs I. J Combin Theory Ser B, 1973, 14: 216-240

[17] Maurer S B. Matroid basis graphs II. J Combin Theory Ser B, 1973, 15: 121-145

[18] Murty U S R. On the number of bases of matroid. In: Proc Second Louisiana Conference on Combinatorics. 1971, 387-410

[19] Oxley J G. Matroid Theory. New York: Oxford University Press, 1992

RIGHTS & PERMISSIONS

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg