# Some Results Involving the Splitting Operation on Binary Matroids

Authors: Naiyer Pirouz; Maruti Mukinda Shikare
Journal: ISRN Discrete Mathematics
 (2012)

---

## Abstract

We obtain some results concerning the planarity and graphicness of the splitting matroids. Further, we explore the effect of splitting operation on the sum of two matroids.


---

## Body

## 1. Introduction

The matroid notations and terminology used here will follow Oxley [1].Fleischner [2] defined the splitting operation for a graph with respect to a pair of adjacent edges as follows.LetG be a connected graph and let v be a vertex of degree at least three in G. If x=vv1 and y=vv2 are two edges incident at v, then splitting away the pair x,y from v results in a new graph Gx,y obtained from G by deleting the edges x and y, and adding a new vertex vx,y adjacent to v1 and v2. The transition from G to Gx,y is called the splitting operation on G. Figure 1 illustrates this construction explicitly.Figure 1Fleischner [2] used the splitting operation to characterize Eulerian graphs. Fleischner [3] also developed an algorithm to find all distinct Eulerian trails in an Eulerian graph using the splitting operation. Tutte [4] characterized 3-connected graphs, and Slater [5] classified 4-connected graphs using a slight variation of this operation.Raghunathan et al. [6] extended the splitting operation from graphs to binary matroids as follows.Definition 1.1.
LetM=M[A] be a binary matroid and suppose x,y∈E(M). Let Ax,y be the matrix obtained from A by adjoining the row that is zero everywhere except for the entries of 1 in the columns labeled by x and y. The splitting matroid Mx,y is defined to be the vector matroid of the matrix Ax,y.
Alternatively, the splitting operation can be defined in terms of circuits of binary matroids as follows.Lemma 1.2 (see [6]).
LetM=(E,𝒞) be a binary matroid on a set E together with the set 𝒞 of circuits and let {x,y}⊆E. Then Mx,y=(E,𝒞') with 𝒞'=𝒞0∪𝒞1, where 𝒞0={C∈𝒞:x,y∈C or x∉C,y∉C}; and  𝒞1={C1∪C2:C1,C2∈𝒞,x∈C1,y∈C2,C1∩C2=ϕ and C1∪C2 contains no member of 𝒞0}.Shikare and Waphare [7] characterized graphic matroids whose splitting matroids are also graphic. In fact, they proved the following theorem.Theorem 1.3 (see [7]).
The splitting operation, by any pair of elements, on a graphic matroid yields a graphic matroid if and only if the matroid has no minor isomorphic to the cycle matroid of any of the four graphs of Figure2.Figure 2
Forbidden graphs.We define a matroid to be planar if it is both graphic and cographic. Let us consider the graph (i) of Figure2. In this graph by splitting away two non-adjacent elements x and y, we will get a matroid which is not planar. This example exhibits the fact that even if the original matroid is planar, there exist pairs of non-adjacent elements x and y such that the splitting matroid is not planar.Now, by considering above example, we prove the following Theorem.Theorem 1.4.
LetG be a planar graph. Then there is at least one pair of non-adjacent edges x and y such that Gx,y is a planar graph.The proof of the theorem is given in Section3.Theorem 1.5 (see [1]).
A binary matroid is graphic if and only if it has no minor isomorphic toF7,F7*,M*(K5), or M*(K3,3).The following example exhibits the fact that there exists a graphic matroidM and a pair of non-adjacent edges, such that the splitting of M with respect to this pair does not yield a graphic matroid.Example 1.6.
Consider the matroidM=M(K5) where K5 is the complete graph on 5 vertices as shown in Figure 3. The matroid has the ground set S={1,2,3,4,5,6,7,8,9,10} and the collection of circuits(1.1)𝒞={{1,2,3},{1,4,5},{1,9,10},{2,4,7},{3,6,9},{4,8,10},{5,8,9},{3,5,7},5{6,7,8},{2,6,10},{1,2,6,9},{1,4,8,9},{1,2,5,7},{1,3,4,7},{2,3,4,5},5{2,4,6,8},{4,6,7,10},{3,7,8,9},{2,7,8,10},{5,6,7,9},{3,5,6,8},5{1,5,8,10},{2,3,9,10},{1,3,6,10},{4,5,9,10},{1,2,7,8,9},{2,3,4,8,9},5{1,2,5,6,8},{2,5,7,9,10},{3,4,5,6,10},{1,4,6,7,9},{1,3,7,8,10},5{1,5,6,7,10},{3,4,7,9,10},{2,3,5,8,10},{2,4,5,6,9},{1,3,4,6,8}}.
The matroidM is graphic and it arises as the cycle matroid of the graph G of Figure 3.
Consider the non-adjacent elements1 and 6 of M. Then, by Lemma 1.2, M1,6=(S,𝒞1,6) is the matroid with ground set S and circuit set 𝒞1,6. By contracting 1 in M1,6, we get a matroid (M1,6)/{1}, which is isomorphic to the matroid M*(K3,3). Thus, by Theorem 1.5, M1,6/{1} is not graphic. By similar arguments, we can check that splitting of M(K5) by any other pair of non-adjacent edges is not graphic. With this observation, we state the following theorem for the splitting matroids.Figure 3Theorem 1.7.
LetM=M(G) be a graphic matroid that is not isomorphic to M(K5). Then there exists at least one pair of non-adjacent edges x and y of E(G) such that Mx,y is graphic.The proof of the theorem is given in Section3.Shikare et al. [8] introduced the concept of generalized splitting operation for a graph with respect to n adjacent edges in the following way.Definition 1.8.
LetG be a connected graph and v a vertex of G with d(v)≥n+1. Let T={x1=vv1,x2=vv2,…,xn=vvn} be a set of adjacent edges incident at v. Then splitting away the edges in T from v results in a new graph GT obtained from G by deleting the edges x1,x2,…,xn and adding a new vertex vT adjacent to v1,v2,…,vn. We say that the graph GT has been obtained from G by splitting away the edges x1,x2,…,xn or in short with respect to the set T.
This construction is illustrated in Figure4 where T={x1,x2,x3}.
Shikare et al. [8] later on extended the notion of the generalized splitting operation from graphs to binary matroids in the following way.Figure 4
Graph and its generalized splitting.Definition 1.9.
LetM=M[A] be a binary matroid on a set S and T a subset of S. Suppose that A is a matrix over GF(2) that represents the matroid M. Let AT be the matrix that is obtained by adjoining an extra row to A with this row being zero everywhere except in the columns corresponding to the elements of T where they take the value 1. Let MT be the matroid represented by the matrix AT. We say that MT has been obtained from M by splitting the set T. The transition from M to MT is called a generalized splitting operation.
In this paper, we explore the effect of the splitting operation on the sum of two matroids and give some application of these results.


## 2. The Splitting Operation on the Sum of Two Matroids

In this section, we provide some definitions and the results which are used in the proof of theorems.Proposition 2.1 (see [1]).
The following statements are equivalent for a graphG:(i)
Gis a planar graph;(ii)
M(G) is a planar matroid;(iii)
M(G) has no minor isomorphic to M(K5) or M(K3,3).Proposition 2.2 (see [1]).
LetT1 and T2 be disjoint subsets of  E(M). Then(i)
(M∖T1)∖T2=M∖(T1∪T2)=(M∖T2)∖T1;(ii)
(M/T1)/T2=M/(T1∪T2)=(M/T2)/T1;(iii)
(M∖T1)/T2=(M/T2)∖T1.Proposition 2.3 (see [7]).
Letx and y be two elements of a binary matroid M. Then (i)
Mx,y=M if and only if x and y are in series or both x and y are coloops in M;(ii)
(Mx,y)/{x}∖{y}≅(Mx,y)/{y}∖{x}≅(Mx,y)∖{x,y}≅M∖{x,y}.Definition 2.4 (see [9]).
IfM1=(E,𝒵1) and M2=(E,𝒵2) are two (not necessarily different) matroids on the same set E then let us define 𝒵1∨𝒵2={X:X=X1∪X2, where X1∈𝒵(M1),X2∈𝒵(M2)}. The matroid M1∨M2=(E,𝒵1∨𝒵2) is called the sum of two matroids.Theorem 2.5 (see [9, 10]).
SupposeM1,M2,…,Mk are matroids on the same set E. If the real matrices A1,A2,…,Ak coordinates the respective matroids M1,M2,…,Mk and all the nonzero entries of all these matrices are algebraically independent over the field Q of the rationales, then the matrix A=[A1A2⋮Ak] coordinates the matroid ∨i=1kMi.Theorem 2.6 (see [6]).
SupposeM is a binary matroid on a set S and x,y∈S. Then M is Eulerian if and only if Mx,y is Eulerian.Definition 2.7 (see [1]).
LetM1 and M2 be matroids on disjoint sets E1 and E2. Let E=E1∪E2 and 𝒵={I1∪I2:I1∈𝒵(M1),I2∈𝒵(M2)}. Then (E,𝒵) is a matroid. This matroid is called the direct sum or 1-sum of M1 and M2 and is denoted M1⊕M2.In the next theorem, Shikare et al. [8] explored the relation between direct sums of two matroids and the splitting operation.Theorem 2.8 (see [8]).
LetM=(S1,𝒞1) and N=(S2,𝒞2) be two binary matroids with S1∩S2=ϕ. Let T1 and T2 be subsets of S1 and S2, respectively. If there is no circuit of M or N containing an odd number of elements of T1 and T2, respectively, then MT1⊕MT2=(M⊕N)T1∪T2.


## 3. Applications

In this section, we use definitions and the results of Section2 to prove Theorems 1.4 and 1.7. We also explore the effect of the splitting operation on the sum of two matroids.Proof of Theorem1.4.
SupposeG is a planar graph. By Proposition 2.1, M(G) is a planar matroid, and therefore M(G) has no minor isomorphic to M(K5) or M(K3,3). We claim that M(Gx,y) is planar for at least one non-adjacent pair of edges x and y of G.
On the contrary, suppose thatM(Gx,y) is not planar for every non-adjacent pair of edges x and y of E(M). This implies that M(Gx,y) has a minor isomorphic to M(K5) or M(K3,3). First, suppose that  M(Gx,y) has M(K3,3) as a minor. Since no two elements in  M(K3,3) are in series, x and y cannot be elements of M(K3,3). Let T1,T2⊆E(M) and x,y∈T1∪T2. We have M(G)x,y/T1∖T2≅M(K3,3). This implies that M(G)x,y/(T1-{x})/{x}∖(T2-{y})∖{y}≅M(K3,3). By Proposition 2.2, we have (M(G)x,y/{x}∖{y})/(T1-{x})∖(T2-{y})≅M(K3,3). Now, by Proposition 2.3 (ii), we have M(G)x,y∖{x,y}/(T1-{x})∖(T2-{y})≅M(K3,3). So M(G)∖{x,y}/(T1-{x})∖(T2-{y})≅M(K3,3). We conclude that M(G) has a minor isomorphic to M(K3,3) which is a contradiction to our assumption that M(G) is a planar matroid. So M(Gx,y) cannot have M(K3,3) as a minor. Now, suppose that  M(Gx,y) has M(K5) as a minor. Then, by similar arguments, we arrive to a contradiction. We conclude that M(Gx,y) cannot have M(K5) as a minor as well. Therefore, M(G)x,y is planar for at least one pair of non-adjacent edges x and y. Consequently, Gx,y is planar for at least one pair of non-adjacent edges x and y.Now, we use Theorem1.3 to prove Theorem 1.7.Proof of Theorem1.7.
LetM be a graphic matroid. Then M is isomorphic to a cycle matroid M(G) of some graph G. Suppose M is not isomorphic to M(K5). By Theorem 1.3, the splitting operation, by any pair of elements, on a graphic matroid yields a graphic matroid if and only if the matroid has no minor isomorphic to the cycle matroid of any of the four graphs of Figure 2. If M has no minor isomorphic to the cycle matroid of any of the four graphs of Figure 2, then there exists at least one pair of non-adjacent edges x and y of E(G) such that (M(G))x,y is graphic. If M has minor isomorphic to the cycle matroid of any of the three graphs (i), (ii), and (iii) of Figure 5, then each of these graphs contains at least one pair of non-adjacent edges x and y of E(G) such that (M(G))x,y is graphic.
As proved in Example1.6 in Section 1, if M=M(K5), there is no pair of non-adjacent edges x and y such that Mx,y is graphic and by Theorem 1.3, M(K5) is only matroid which has this property and this completes the proof.Figure 5In the next theorem, we explore the relation between the sum of two matroids and the splitting operation.Theorem 3.1.
LetM=(S,𝒞1) and N=(S,𝒞2) be binary matroids on the same underlying set S. If x,y∈S, then Mx,y∨Nx,y=(M∨N)x,y.Proof.
LetA and B be the matrices that represent M and N, respectively. The matrix representation for Mx,y and Nx,y, say A′ and B′, is obtained from A and B, respectively, by adjoining extra rows to A and B, which are zero everywhere except in the columns corresponding to the elements x and y where it takes the value 1.
By Theorem2.5, the matrix representation for (Mx,y∨Nx,y) is the matrix [A′B′] with two equal rows. By replacing a row by the sum of that row and the row which is equal to that, we get one zero row. By deleting the zero row, we obtain a matrix representation of the matroid (Mx,y∨Nx,y).
The matrix representation of(M∨N)x,y, say D, can be obtained by adjoining one extra row to the matrix [AB] which is zero everywhere except in the columns corresponding to the elements x and y where it takes the value 1. We observe that D=[A′B′]. This completes the proof.It is well known that a graph is Eulerian if and only if its edge set can be partitioned into disjoint circuits. Generalizing this graph theoretic concepts, Welsh [11] defined Eulerian matroid. A matroid (S,𝒞) is said to be Eulerian if the ground set S is the union of disjoint circuits of the matroid. Further, Welsh [11] proved that a binary matroid is Eulerian if and only if its dual matroid is bipartite.The following theorem states that the splitting of the sum of two binary Eulerian matroids is the sum of the corresponding splitting matroids.Theorem 3.2.
LetM=(S,𝒞1) and N=(S,𝒞2) be binary matroids with x,y∈S. Then M and N are Eulerian if and only if Mx,y∨Nx,y is Eulerian.Proof.
LetA and B be the matrices that represent M and N, respectively. Suppose M and N are Eulerian matroids. By Theorem 2.6, Mx,y and Nx,y are Eulerian. Let A' and B' be the matrices obtained from A and B by adjoining extra rows, which are zero everywhere except in the columns corresponding to the elements x and y where they take the value 1. Then the matrix D=[A′B′] is a matrix representation of the matroid Mx,y∨Nx,y. Since the number of 1’s in each row of the matrix D is even, the matroid Mx,y∨Nx,y is Eulerian.
The converse part of proof is straightforward.Using Theorem3.2, we prove that the splitting of the sum of n binary Eulerian matroids is the sum of the corresponding splitting matroids.Theorem 3.3.
LetM1=(S,𝒞1), M2=(S,𝒞2),…, Mn=(S,𝒞n) be binary matroids with x,y∈S. Then M1,M2,…,Mn are Eulerian if and only if (M1)x,y∨(M2)x,y∨⋯∨(Mn)x,y is Eulerian.Proof.
LetA1,A2,…,An be the matrices that represent M1,M2,…,Mn, respectively. Suppose that  M1,M2,…,Mn are Eulerian matroids. By Theorem 2.6, (M1)x,y,(M2)x,y,…,(Mn)x,y are Eulerian. Let A1',A2',…,An' be the matrices obtained from A1,A2,…,An by adjoining extra rows, which are zero everywhere except in the columns corresponding to the elements x and y where they take the value 1. Then the matrix D=[A1′A2′⋮An′] is a matrix representation of the matroid (M1)x,y∨(M2)x,y∨⋯∨(Mn)x,y. Since the number of 1’s in each row of the matrix D is even, the matroid (M1)x,y∨(M2)x,y∨⋯∨(Mn)x,y is Eulerian.
The converse part of proof is straightforward.Theorem 3.4.
LetM=(S1,𝒞1) and N=(S2,𝒞2) be two binary matroids with S1∩S2=ϕ. Let T1 and T2 be subsets of S1 and S2, respectively. Then M and N are Eulerian if and only if (M⊕N)T1∪T2 is Eulerian.Proof.
LetM=(S1,𝒞1) and N=(S2,𝒞2) be two binary matroids with S1∩S2=ϕ. Let T1 and T2 be subsets of S1 and S2, respectively. Suppose the  M and Nare Eulerian. Then, S1 and S2 can be expressed as a disjoint unions of circuits of M and N, respectively. Suppose that S1=C1∪C2∪⋯∪Cm and S2=C1′∪C2′∪⋯∪Cn′. Then S1∪S2=C1∪C2∪⋯∪Cm∪C1′∪C2′∪⋯∪Cn′ is a disjoint union of circuits of M⊕N. So M⊕N is Eulerian. By Theorem 2.8, (M⊕N)T1∪T2 is Eulerian.
The converse part of the proof is straightforward.



---

*Source: 406147-2012-12-16.xml*