Abstract
The intersection graph of bases of a matroid M=(E, B) is a graph G=GI (M) with vertex set V(G) and edge set E(G) such that V(G)=B(M) and E(G)={BB′: |B ∩ B′|≠0, B, B′∈ B(M), where the same notation is used for the vertices of G and the bases of M. Suppose that |V (GI (M))| =n and k1 + k2... kp = n, where ki is an integer, i =1, 2,..., p. In this paper, we prove that there is a partition of V (GI (M)) into p parts V1, V2,..., Vp such that |Vi| = ki and the subgraph Hi induced by Vi contains a ki-cycle when ki ≥3, Hi is isomorphic to K2 when ki =2 and Hi is a single point when ki =1.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Maurer S B. Matroid basis graph I [J]. J Combin Theory Ser B, 1973, 14: 216–240.
Maurer S B. Matroid basis graph II [J]. J Combin Theory Ser B, 1973, 15: 121–145.
Li P, Liu G Z. The edge connectivity of circuit graphs of matroids[C]//International Conference on Computational Science 2007, Part III, LNCS 4489. Berlin: Springer-Verlag, 2007: 440–443.
Li P, Liu G Z. Cycles in matroid circuit graphs [J]. Graphs and Combinatorics, 2007, 23(4): 425–431.
Liu G Z, Li P. Paths in circuit graphs of matroids [J]. Theoretical Computer Science, 2007, 23(4): 425–431.
Li P, Liu G Z. Hamiltonian cycles in matroid circuit graphs [J]. Computers and Mathematics with Applications, 2008, 55: 654–659.
Li P, Liu G Z. The connectivity and minimum degree of circuit graphs of matroids [J]. Acta Mathematica Sinica, English Series, 2010, 26(2): 353–360.
Cummins R L. Hamiltonian circuits in tree graphs [J]. IEEE Trans Circuits Syst, 1966, 13: 82–90.
Bondy J A. Pancyclic graphs: II [C]// Proceedings of the Second Louisiana Conference on Combinatorics, Graph Theory and Computing. Boton Rouge: AMS, 1971:167–172.
Holzmann C A, Harary F. On the tree graph of a matroid [J]. SIAM J Appl Math, 1972, 22: 187–193.
Zhang Y, Yu Q, Liu G. Edge disjoint Hamilton cycles in intersection graphs of bases of matroids[J]. Utilitas Math, 2013, 90: 327–334.
Oxley J G. Matroid Theroy [M]. New York: Oxford University Press, 1992.
Bondy J A, Murty U S R. Graph Theory with Applications[M]. New York: Macmillan Press, 1976.
Author information
Authors and Affiliations
Corresponding author
Additional information
Foundation item: Supported by the National Natural Science Foundation of China (31601209), and the Natural Science Foundation of Hubei Province (2017CFB398)
Rights and permissions
About this article
Cite this article
Zhang, Y., Chi, H. Vertex disjoint cycles in intersection graphs of bases of matroids. Wuhan Univ. J. Nat. Sci. 22, 461–464 (2017). https://doi.org/10.1007/s11859-017-1273-y
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11859-017-1273-y