Discussiones Mathematicae Graph Theory 29(3) (2009) 629-644
doi: 10.7151/dmgt.1469

[BIBTex] [PDF] [PS]

FORBIDDEN-MINOR CHARACTERIZATION FOR THE CLASS OF GRAPHIC ELEMENT SPLITTING MATROIDS

Kiran Dalvi*,  Y.M. Borse**  and  M.M. Shikare**

*Department of Mathematics
Government College of Engineering, Pune 411 005, India
e-mail: kiran_dalvi111@yahoo.com

**Department of Mathematics
University of Pune, Pune 411 007, India
e-mail: ymborse@math.unipune.ernet.in
e-mail: mms@math.unipune.ernet.in

Abstract

This paper is based on the element splitting operation for binary matroids that was introduced by Azadi as a natural generalization of the corresponding operation in graphs. In this paper, we consider the problem of determining precisely which graphic matroids M have the property that the element splitting operation, by every pair of elements on M yields a graphic matroid. This problem is solved by proving that there is exactly one minor-minimal matroid that does not have this property.

Keywords: binary matroid, graphic matroid, minor, splitting operation, element splitting operation.

2000 Mathematics Subject Classification: 05B35.

References

[1] G. Azadi, Generalized splitting operation for binary matroids and related results (Ph.D. Thesis, University of Pune, 2001).
[2] Y.M. Borse, M.M. Shikare and Kiran Dalvi, Excluded-Minor characterization for the class of Cographic Splitting Matroids, Ars Combin., to appear.
[3] H. Fleischner, Eulerian Graphs and Related Topics, Part 1, Vol. 1 (North Holland, Amsterdam, 1990).
[4] A. Habib, Some new operations on matroids and related results (Ph.D. Thesis, University of Pune, 2005).
[5] F. Harary, Graph Theory (Addison-Wesley, Reading, 1969).
[6] J.G. Oxley, Matroid Theory (Oxford University Press, Oxford, 1992).
[7] T.T. Raghunathan, M.M. Shikare and B.N. Waphare, Splitting in a binary matroid, Discrete Math. 184 (1998) 267-271, doi: 10.1016/S0012-365X(97)00202-1.
[8] A. Recski, Matroid Theory and Its Applications (Springer Verlag, Berlin, 1989).
[9] M.M. Shikare and G. Azadi, Determination of the bases of a splitting matroid, European J. Combin. 24 (2003) 45-52, doi: 10.1016/S0195-6698(02)00135-X.
[10] M.M. Shikare, Splitting lemma for binary matroids, Southeast Asian Bull. Math. 32 (2007) 151-159.
[11] M.M. Shikare and B.N. Waphare, Excluded-Minors for the class of graphic splitting matroids, Ars Combin., to appear.
[12] P.J. Slater, A classification of 4-connected graphs, J. Combin. Theory 17 (1974) 281-298, doi: 10.1016/0095-8956(74)90034-3.
[13] W.T. Tutte, A theory of 3-connected graphs, Indag. Math. 23 (1961) 441-455.
[14] D.J.A. Welsh, Matroid Theory (Academic Press, London, 1976).

Received 15 October 2008
Revised 17 December 2008
Accepted 17 December 2008