![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
Abstract
In general, the splitting operation on a binary matroid does not preserve the connectivity of
In this paper, we provide sufficient conditions to preserve
-connectedness of a binary matroid under splitting operation. As a consequence, for an
-connected binary matroid
, we give a precise characterization of when the splitting matroid
is
-connected.
1 Introduction
We refer to Oxley [Citation1] for standard terminology in graphs and matroids. The matroids under consideration are loopless. For a matroid let
and
denote the ground set and the rank function of
respectively. For sets
and
, let
denote the set
.
Fleischner [Citation2] defined the splitting operation for graphs with respect to a pair of adjacent edges. As an extension of this operation to binary matroids, Raghunathan, Shikare and Waphare [Citation3] defined the splitting operation for binary matroids with respect to a pair of elements. The effects of the splitting operation on various parameters of a matroid like graphicness, cographicness, and connectedness have been well studied in the literature, for example,see [4–6,3,7,8Citation[4]Citation[5]Citation[6]Citation[3]Citation[7]Citation[8]].
The splitting operation for binary matroids with respect to any set which is a generalization of the splitting operation with respect to a pair of elements, is defined by Shikare, Azadi and Waphare [Citation9] as follows.
Definition 1.1
[Citation9]
Let be a binary matroid with standard matrix representation
over the field
and let
Let
be the matrix obtained by adjoining one extra row to the matrix
whose entries are 1 in the columns labeled by the elements of the set
and zero otherwise. The vector matroid of the matrix
denoted by
is called as the splitting matroid of
with respect to
and the transition from
to
is called as the splitting operation with respect to
(See Remark 4.3.)
The splitting operation on a matroid is related to a lift of
A matroid
is a coextension of
if
for some nonempty subset
of
If
then
is a lift of
Let
be a binary matroid and
and
be a lift of
by
with
such that
is a cocircuit in
Then
In general, the splitting operation does not preserve the connectivity of a given matroid. Borse and Dhotre [Citation5] obtained the following result to get a connected splitting matroid when
Theorem 1.2
[Citation5]
Let be a connected and vertically
-connected binary matroid and
with
Suppose every cocircuit
of
with
has size at least
and further,
does not contain a
-circuit of
. Then
is connected.
Malvadkar, Shikare and Dhotre [Citation10] obtained the following generalization of Theorem 1.2 by assuming an additional condition on the girth of
Theorem 1.3
[Citation10]
Let be an integer and
be an
-connected, vertically
-connected binary matroid with
and girth at least
Suppose
with
Then the matroid
is
-connected if and only if for
with
there is a circuit
in
such that
is odd and
However, in Lemma 3.7 we prove that an -connected, vertically
-connected binary matroid
with
and girth at least
is
-connected. Therefore the matroid
considered in Theorem 1.3 is actually
-connected, which is a stronger condition on
to preserve
-connectedness under the splitting operation. Without assuming this stronger condition, we generalize Theorem 1.2 as follows.
Theorem 1.4
Let be an integer and
be an
-connected and vertically
-connected binary matroid with
and
with
Suppose
is not an
-circuit in
and for every cocircuit
of
intersecting
and further,
is not an
-circuit of
Then
is
-connected.
We also obtain, in Theorem 4.1, some necessary conditions for to be
-connected. On combiningTheorems 1.4, 4.1, Lemma 3.7 and Theorem 1.3, we prove the following characterization for the matroid
to be
-connected.
Theorem 1.5
Let and
be an
-connected binary matroid with
and
with
Then the following statements are equivalent.
(1) | The matroid |
(2) | For every cocircuit |
(3) | For |
The circuits, cocircuits and rank function of the splitting matroid are given in the second section. In Section 3, we provide some basic concepts and results regarding connectedness and obtain few lemmas. The proofs of the main results are given in the last section. We also discuss the sharpness of Theorem 1.4 in the remark given at the last section.
2 Circuits and cocircuits of ![](//:0)
![](//:0)
It is clear from Definition 1.1 that the ground sets of the matroids and
are same. Further,
if
is a cocircuit of
Moreover,
is a cocircuit of
if no proper subset of
is a cocircuit in
Mills [Citation11] characterized the cocircuits of the splitting matroid
in terms of the cocircuits of
when
Theorem 2.1
[Citation11]
Let be a binary matroid with the collection of cocircuits
and let
Suppose
does not contain a cocircuit of
Then each cocircuit of
other than
belongs to one of the following collections.
(i) |
|
(ii) |
|
(iii) |
(iv) |
|
Azanchiler [Citation12] generalized Theorem 2.1 for arbitrary as follows.
Theorem 2.2
[Citation12], pp. 35
Let be a binary matroid with the collection of cocircuits
and
with
Suppose
does not contain a cocircuit of
Then each cocircuit of
other than
belongs to one of the following collections.
(i) |
|
(ii) |
|
(iii) |
(iv) |
|
The circuits and the rank function of the splitting matroid are given in [Citation9].
Lemma 2.3
[Citation9]
Let be a binary matroid and
and
be the collection of circuits of
. Then the collection of circuits of
is
, where
and
Lemma 2.4
[Citation9]
Let be a binary matroid,
such that
and
does not contain a cocircuit of
Suppose
and
are the rank functions of the matroid
and
, respectively, and
Then
(i) , if
does not contain a circuit of
containing an odd number of elements of
;
(ii) , otherwise;
(iii)
3 Connected and vertically connected matroids
We provide here some basic definitions and results given in [Citation1]. Let be an integer and
be a matroid with ground set
and rank function
An
-separation of
is a partition
of
such that min
and
If
is
-separated for some
then connectivity
of
is the minimum
such that
has a
-separation; otherwise it is
An
-separation
of
is a vertical
-separation if min
The vertical connectivity
of
is the minimum
such that
has a vertical
-separation if
has two disjoint cocircuits, otherwise
. The matroid
is
-connected if
and it is vertically
-connected if
Obviously, every
-connected matroid is vertically
-connected. If
contains a circuit, then its girth, denoted by
is the minimum circuit size. Similarly, if
contains a cocircuit, then its cogirth is the minimum cocircuit size.
We need the following known results.
Theorem 3.1
[Citation1], pp. 279
If a matroid is not isomorphic to any uniform matroid
with
then
Theorem 3.2
[Citation1], pp. 273
If and
is an
-connected matroid with
then all circuits and all cocircuits of
have at least
elements.
Lemma 3.3
[Citation1], pp. 274
Let be an
-connected matroid having at least
elements. Then
has no
-element subset that is both a circuit and a cocircuit.
Lemma 3.4
[Citation1], pp. 70
Let be a matroid and let
Then
is a cocircuit if and only if
is a hyperplane of
Corollary 3.5
[Citation4]
Let be a matroid and let
such that
Then
contains a cocircuit of
Lemma 3.6
Let be an integer and let
be an
-connected, vertically
-connected binary matroid with
Then the cogirth of
is at least
Proof
By Theorem 3.2, the cogirth of is at least
Suppose it is
Then there is a cocircuit
of
with
Let
By Lemma 3.4,
is a hyperplane and so
Again by Theorem 3.2,
and
Therefore
If
then
is a vertical
-separation of
a contradiction. Hence
Therefore, if
then
is a vertical
-separation of
again a contradiction. Consequently,
This implies that every
-element set in
is a circuit. It follows that
is isomorphic to the uniform matroid
where
If then
and so
contains the uniform matroid
as a minor, a contradiction to the fact that
is binary. Hence
Therefore
is isomorphic to
This implies that
is the cycle matroid of the connected graph on two vertices and
edges. It follows that
, where
is the graph obtained from a triangle by adjoining
edges parallel to one of the edge. As
contains a vertex of degree two, it is not 3-connected and so
is not vertically 3-connected. Therefore
is not vertically
-connected, a contradiction. This completes the proof. □
Lemma 3.7
Let be an integer and let
be an
-connected, vertically
-connected binary matroid with
and girth at least
Then
is
-connected.
Proof
Since is vertically
-connected,
Also, the girth
of
is at least
By Lemma 3.6, the cogirth of
is also at least
Let
be the rank of
Then
and therefore
Suppose
is isomorphic to the uniform matroid
for some
with
Then
Suppose
Then
is a circuit and hence the cogirth of
is
a contradiction. Thus
This implies that
contains
as a minor. Hence
is a minor of the binary matroid
a contradiction. Therefore
is not isomorphic to the uniform matroid
with
Now, by Theorem 3.1,
Hence
is
-connected. □
4 Main results
In the following theorem, we provide some necessary conditions for the splitting matroid to be
-connected.
Theorem 4.1
Let and
be an
-connected and vertically
-connected binary matroid with
and
with
Suppose the splitting matroid
is
-connected and
is a cocircuit of
intersecting
Then
(i)
(ii) neither nor
is an
-circuit in
if
is even.
Proof
By Theorem 3.2, every circuit of has size at least
and, by Lemma 3.6, every cocircuit of
has size at least
Similarly, every cocircuit of
contains at least
elements. As
does not contain any cocircuit of
By Lemma 2.4 (iii),
Suppose is a cocircuit of
containing
elements of
If
is a subset of
then, by Theorem 2.2 (i),
is a cocircuit of the splitting matroid
Further, if
is not a subset of
then
is a cocircuit of
by Theorem 2.2 (iii). In both the cases,
is a cocircuit of
Therefore,
giving
Thus
This proves (i).
We now prove (ii). Suppose is even. Assume that
is an
-circuit of
In a binary matroid, intersection of a circuit and a cocircuit contains an even number of elements. Therefore
is even. Consequently,
is even as
is even. Hence, by Lemma 2.3,
is an
-circuit of
Already
is an
-cocircuit of
This is a contradiction by Lemma 3.3. Assume that
is an
-circuit of
Then, by Lemma 2.3,
is also a circuit of
Further, by Definition 1.1,
is a cocircuit of
This is a contradiction by Lemma 3.3. □
We now prove Theorem 1.4.
Proof of Theorem 1.4
By Theorem 3.2, the girth of is at least
and, by Lemma 3.6, the cogirth of
is at least
Hence
does not a contain cocircuit of
as
Therefore, by Lemma 2.4 (iii),
We prove the result by contradiction. Suppose
is not
-connected. Then it has an
-separation
Therefore
and
Suppose
Then
is independent in
and so, by Lemma 2.3,
is independent in
also. Suppose
contains a cocircuit
of
Then
and hence, by Theorem 3.2,
is not a cocircuit of
By Theorem 2.2,
belongs to one of the three classes
,
or
Suppose
Then
where
is a cocircuit of
containing
Then, by hypothesis,
and so
a contradiction. Suppose
Then
where
and
are mutually disjoint cocircuits of
and each of them contains at least one element of
Since
and
we have
a contradiction. Hence
Therefore
where
is a cocircuit of
intersecting
but not containing
Then
where
Hence
a contradiction. Thus
does not contain a cocircuit of
Hence This gives
which is a contradiction. Similarly, we get a contradiction if
Therefore and
If
and
then,
and so
is a vertical
-separation of
a contradiction. Hence
or
Without loss of generality assume that
Therefore every subset of
containing
elements is dependent in
and so in
This shows that every subset of
of size
is an
-circuit of
If
then
is a minor of the binary matroid
which is a contradiction. Hence
Thus
is an
-circuit of
By Lemma 3.6,
does not contain a cocircuit of
This gives
Now, if then
This implies that
is an
-separation of
a contradiction. Hence
If
does not contain a cocircuit of
then
a contradiction to Lemma 2.4 (iii).
Thus contains a cocircuit
of
Therefore
As cogirth of
is at least
is not a cocircuit of
Further,
as
is not an
-circuit of
Therefore
By Theorem 2.2,
for some
Suppose
Then
for some cocircuit
of
containing
Therefore
Hence
This implies that
Since
is an
-circuit,
is an
-circuit of
a contradiction to the assumption that
is not an
-circuit of
. Suppose
Then
for some cocircuit
of
intersecting
but not containing
Then
and so
This gives
Hence
is an
-circuit of
a contradiction. Therefore
Hence
where
and
are mutually disjoint cocircuits of
and each of them contains at least one element of
Since
and
we have
a contradiction. □
We prove Theorem 1.5, which is restated here for convenience. In view of Lemma 3.7, the equivalence of statements (1) and (3) follows directly from Theorem 1.3. However, we provide a shorter proof of the same.
Theorem 4.2
Let and
be an
-connected binary matroid with
and
with
Then the following statements are equivalent.
(1) | The matroid |
(2) | For every cocircuit |
(3) | For |
Proof
Since is an
-connected, it is
-connected as well as vertically
-connected. Further, by Theorem 3.2 every circuit and every circuit of
contains at least
elements. Therefore
does not contain a cocircuit of
as
(1) (2) follows from Theorem 4.1.
(2) (1) follows from Theorems 4.1 and 3.2.
(1) (3). Suppose
is
-connected but (3) does not hold. Then there is a set
with
such that
for every circuit
in
with
an odd integer. Let
Then
and, by Lemma 2.4 (i),
Since
is not a circuit of
by Lemma 2.3,
is independent in
and so
By Theorem 3.2,
does not contain a cocircuit of
Therefore
by Corollary 3.5. Hence
Thus
is an
-separation of
a contradiction.
(3) (1). Assume that (3) holds but (1) does not hold. Then
has an
-separation
Therefore min
and
Suppose and
By Lemma 2.4,
Hence
is an
-separation of
, a contradiction to the fact that
is
-connected.
Therefore we may assume that By (3) and Lemma 2.4 (ii),
Consequently,
This shows that
is an
-separation of
a contradiction. □
Remark 4.3
In the following example, we show that the condition on the matroid given in Theorem 1.4 that
is vertically
-connected cannot be dropped. The graph
of (a) is 2-connected but not 3-connected. Hence its cycle matroid
is 2-connected but not vertically 3-connected. Let
where
and
are the edges of
as shown in (a). Then
satisfies the hypothesis of Theorem 1.4. The graph
obtained by splitting away the edges
and
is shown in (b). Clearly,
However,
is not 2-connected and so
is not 2-connected.
(a) The graph
Fig. 1 Splitting of a graph.
Notes
Peer review under responsibility of Kalasalingam University.
References
- Oxley J.G. Matroid Theory 1992 Oxford University Press Oxford
- Fleischner H. Eulerian Graphs and Related Topics Part 1, Vol. 1 1990 North Holland Amsterdam
- Raghunathan T.T. Shikare M.M. Waphare B.N. Splitting in a binary matroid Discrete Math. 184 1998 267 271
- Borse Y.M. A note on n-connected splitting-off matroids Ars Combin. 128 2016 279 286
- Borse Y.M. Dhotre S.B. On connected splitting matroids Southeast Asian Bull. Math. 36 1 Special Issue: Special Issue: International Conference on Discrete Mathematics 2012 17 21
- Borse Y.M. Shikare M.M. Dalvi K.V. Excluded-Minors for the class of cographic splitting matroids Ars Combin. 115 2014 219 237
- Shikare M.M. Dalavi K.V. Dhotre S.B. Splitting-off operation for binary matroids and its applications Graphs Combin. 27 6 2011 871 882
- Shikare M.M. Waphare B.N. Excluded-Minors for the class of graphic splitting matroids Ars Combin. 97 2010 111 127
- Shikare M.M. Azadi G. Waphare B.N. Generalized splitting operation for binary matroids and its applications J. Indian Math. Soc. New Ser. 78 1–4 2011 145 154
- Malavadkar P.P. Shikare M.M. Dhotre S.B. A characterization of n-connected splitting matroids Asian-Eur. J. Combin. 7 4 2014 7 Article 14500600
- Mills A. On the cocircuits of a splitting matroid Ars Combin. 89 2008 243 253
- Azanchiler H. (Ph.D. Thesis) Some New Operation on Matroids and Related Results 2005 University of Pune