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 e of G if G has 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 AW. Pancyclic graphs II. J Combin Theory Ser B, 1976, 20: 41-46

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

[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. ICCS 2007, 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 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, 1992, New York: Oxford University Press