Commenced in January 2007
Frequency: Monthly
Edition: International
Paper Count: 87760
A Forbidden-Minor Characterization for the Class of Co-Graphic Matroids Which Yield the Graphic Element-Splitting Matroids
Authors: Prashant Malavadkar, Santosh Dhotre, Maruti Shikare
Abstract:
The n-point splitting operation on graphs is used to characterize 4-connected graphs with some more operations. Element splitting operation on binary matroids is a natural generalization of the notion of n-point splitting operation on graphs. The element splitting operation on a graphic (cographic) matroid may not yield a graphic (cographic) matroid. Characterization of graphic (cographic) matroids whose element splitting matroids are graphic (cographic) is known. The element splitting operation on a co-graphic matroid, in general may not yield a graphic matroid. In this paper, we give a necessary and sufficient condition for the cographic matroid to yield a graphic matroid under the element splitting operation. In fact, we prove that the element splitting operation, by any pair of elements, on a cographic matroid yields a graphic matroid if and only if it has no minor isomorphic to M(K4); where K4 is the complete graph on 4 vertices.Keywords: binary matroids, splitting, element splitting, forbidden minor
Procedia PDF Downloads 279