Applied Mathematics, 2010, 1, 244-249
doi:10.4236/am.2010.13030 Published Online September 2010 (http://www.SciRP.org/journal/am)
Reinforcing a Matroid to Have k Disjoint Bases
Hong-Jian Lai1,2, Ping Li2, Yanting Liang2, Jinquan Xu3
1College of Mathematics and System Sciences, Xinjiang University, Urumqi, China
2Department of Mathematics, West Virginia University, Morgantown, USA
3Department of Mathematics, Huizhou University, Huizhou, China
Received May 14, 2010; revised July 29, 2010; accepted August 2, 2010
Abstract
Let ()
M

denote the maximum number of disjoint bases in a matroid
M
. For a connected graph G, let
()=( ())GMG

 , where ()
M
G is the cycle matroid of G. The well-known spanning tree packing theo-
rem of Nash-Williams and Tutte characterizes graphs G with ()Gk

. Edmonds generalizes this theorem
to matroids. In [1] and [2], for a matroid
M
with ()
M
k

, elements ()eEM

with the property that
()
M
ek

 have been characterized in terms of matroid invariants such as strength and

-partitions. In
this paper, we consider matroids
M
with ()<
M
k

, and determine the minimum of |()||( )|
E
MEM


,
where
M
 is a matroid that contains
M
as a restriction with both ()=()rM rM

and ()
M
k

. This
minimum is expressed as a function of certain invariants of
M
, as well as a min-max formula. These are
applied to imply former results of Haas [3] and of Liu et al. [4].
Keywords: Disjoint Bases, Edge-Disjoint Spanning Trees, Spanning Tree Packing Numbers, Strength,
Fractional Arboricity
1. Introduction
In this paper, we use N and Q to denote the set of
all natural numbers and the set of all positive fractional
numbers, respectively, and consider finite matroids and
graphs. Undefined notations and terminology can be
found in [5] or [6] for matroids, and [7] for graphs. Thus
for a connected graph G, ()G

denotes the number of
components of G. For a matroid
M
,
M
r (or r,
when the matroid
M
is understood from the context)
denotes the rank function of
M
, and ()EM , ()
I
M,
()CM and ()BM denote the ground set of
M
, and
the collections of independent sets, the circuits, and the
bases of
M
, respectively. Furthermore, if
M
is a ma-
troid with =()EEM, and if
X
E, then
M
X

is
the restricted matroid of
M
obtained by deleting the
elements in
X
from
M
, and /
M
X is the matroid
obtained by contracting elements in
X
from
M
. As in
[5] or [6], we use
M
e for {}
M
e and /
M
e for
/{}
M
e.
For a matroid
M
, let ()
M

denote the maximum
number of disjoint bases of
M
. For a graph G, define
()=( ())GMG

 , where ()
M
G denotes the cycle ma-
troid of G. Thus if G is a connected graph, then
()G

is the spanning tree packing number of G.
Readers are referred to [8] for a survey on ()G

. The
well-known spanning tree packing theorem of Nash-
Williams [9] and Tutte [10] characterizes graphs with k
edge-disjoint spanning trees, for any integer >0k.
Edmonds [11] proved the corresponding theorem for
matroids.
Let >0k be an integer. For any matroid
M
with
()
M
k

, we are interested in finding elements
()eEM

that have the property that ()
M
ek


.
Characterizations of all such elements have been found
in [1] and [2]. For a graph G, the problem of determin-
ing which edges should be added to G so that the re-
sulting graph has k edge-disjoint spanning trees has
been studied, see Haas [3] and Liu et al. [4], among oth-
ers. As the arguments in these papers are involved verti-
ces, it is natural to consider the possibility of extending
these results to matroids. Since matroids in general do
not have a concept corresponding to vertices, one can no
longer add an element to a matroid as adding an edge in
graphs. Therefore, we need to reformulate the problem
so that it would fit the matroid setting while generalizing
the graph theory results.
Let
M
be a matroid and kN. If there is a ma-
troid
M

with ()=()rM rM

and ()
M
k

 such
that
M

has a restriction isomorphic to
M
(we then

H.-J. LAI ET AL.
245
view
M
as a restriction of
M
), then
M

is a
()k

-extension of
M
. We shall show that any ma-
troid has a ()k

-extension. We then define (,)
F
Mk
to be the minimum integer >0l such that
M
has a
()k

-extension
M
 with |()||( )|=EMEM l .
The main purpose of this paper is to determine (,)
F
Mk
in terms of other invariants of
M
.
By definition, if
M
is a matroid with ()=0rM ,
then kN , ()
M
k

. Accordingly, for a connected
graph G, if |()|=1VG , then ()Gk

 for any
kN. For a graph G, 1()aG, the edge arboricity of
G, is the minimum number of spanning trees of G
whose union equals ()EG . For a matroid, we define the
similar concept 1()
M

, which is the minimum number
of bases of
M
whose union equals ()EM . The fol-
lowing theorems are well known.
Theorem 1.1 Let G be a connected graph with
|()|>1VG , and let >0k be an integer. Each of the
following holds.
1) (Nash-Williams [9] and Tutte [10]) ()Gk

 if
and only if ()
X
EG , ||(( )1)Xk GX

.
2) (Nash-Williams [12]) 1()aG k if and only if
()
X
EG , ||(|( [])|( []))
X
kVGX GX

.
Theorem 1.2 (Edmonds [11]) Let
M
be a matroid
with ()>0rM . Each of the following holds.
1) ()
M
k

 if and only if ()
X
EM ,
|( )|(( )())EMX krMrX .
2) 1()
M
k

 if and only if ()
X
EM ,
|| ()
X
kr X.
Let
M
be a matroid with rank function r. For any
subset ()
X
EM with ()>0rX , the density of
X
is
||
()= .
()
M
M
X
dX rX
When the matroid
M
is understood from the context,
we often omit the subscript
M
. We also use ()dM for
(( ))dEM. Following [13] and [14], the strength ()
M

and the fractional arboricity ()
M

of
M
are respec-
tively defined as
  
   
=min: <,
=max:>0 .
MdMXrXrM
andMdXr X


(1)
Thus Theorem 1.2 above indicates that
  
1
=, =.MMandMM     (2)
We assume that
M
is a matroid with ()>0rM . A
subset ()
X
EM is an

-maximal subset and
|
M
X is an

-maximal restriction if for any subset
()YEM that properly contains
X
, we have
(|)<(|)
M
YMX

 . In [1] and [2], it has been proved
that any matroid
M
has a unique decomposition based
on its

-maximal subsets.
Theorem 1.3 ([1] and [2]) Let
M
be a matroid with
()>0rM . Then each of the following holds.
1) There exist an integer mN, and an m-tuple
12
(, ,...,)
m
lll of rational numbers in Q such that


12
=<<...< =,
m
M
lllG  (3)
and a sequence of subsets
21
...= ();
m
J
JJEM  (4)
such that for each i with 1im , |i
M
J is an

-
maximal restriction of
M
with (|)=
ii
M
Jl

.
2) The integer m and the sequences (4) and (3) are
uniquely determined by
M
.
For a matroid
M
, the m-tuple 12 ( ,,...,)
m
lll and the
sequence in (4) will be referred as the

-spectrum and
the

-decomposition of
M
, respectively. For each
subscript j with 1jm

, we refer
j
J
to be the set
corresponding to
j
l. Our main result can now be stated
as follows.
Theorem 1.4 For kN

, let
M
be a matroid with
()
M
k


. If ()<
M
k

, define ()=
ik
J; and if
()
M
k

, let ()ik denote the smallest subscript in (3)
such that ()ik
lk. Then
1) () ()
(,)=(() ())|()|
ik ik
FMkkrM rJEMJ

.
2) ()
(,)={( /)|/ |}
max XEM
F
MkkrMXMX
.
In the next section, we shall present some of the useful
properties related to the strength and the fractional ar-
boricity of a matroid
M
, and to the decomposition of
M
. Section 3 will be devoted to the proofs of the main
results. In the last section, we shall show some applica-
tions of our main results.
2. Preliminaries
Both ()
M

and ()
M

have been studied by many,
see [14-16] and [17], among others. From the definition
of (),()dM M

and ()
M

, we immediately have, for
any matroid
M
with ()>0rM ,
()() ().
M
dM M



 (5)
A matroid
M
satisfying ()=()
M
M

 is called a
uniformly dense matroid. Both ()
M

and ()
M

can
also be described by their behavior in some parallel ex-
tension of the matroid $M$.
Definition 2.1 Let
M
be a matroid and let
:( )EM N

 be a function. For each ()eEM, let
12 ()
={ ,,,}
e
e
Xee e

 be a set such that =
ee
XX


,
,()ee EM


 with ee


. The

-parallel extension
of
M
, denoted by
M

, is obtained from
M
by re-
placing each element ()eEM

by a class of ()e

parallel elements e
X
. Thus () ()= e
eEM
EM X


 such
that a subset ()YEM

 is independent in
M

if and

H.-J. LAI ET AL.
246
only if both {(): }
e
eEM XY is independent in
M
and ()eEM , ||1
e
XY

. For tN

, if
()eEM , ()=et

is a constant function, we write
t
M
for
M

, and call t
M
the t-parallel extension of
M
.
Let 1
={ :()}()EeeEM EM

 . Then the bijec-
tion 1 ee between ()EM and E yields a matroid
isomorphism between
M
and |
M
E

. Under this
bijection, we shall view that =|
M
ME

 is a restric-
tion of
M

.
Theorem 2.2 (Theorem 4 of [14]) Let
M
be a ma-
troid and let >0st be integers. Then
1) ()
s
Mt   if and only if ()
t
M
s

.
2) ()
s
Gt   if and only if ()
t
M
s

.
Theorem 2.3 (Theorem 6 of [14]) Let
M
be a ma-
troid. The following are equivalent.
1) ()=()
M
dM

.
2) ()=()
M
dM

.
3) ()=()
M
M

 .
4) ()=
s
Mt 
, for some integers >0st, and t
M
,
the t-parallel extension of
M
, is a disjoint union of
s
bases of
M
.
5) ()=
s
Mt  , for some integers >0st, and t
M
,
the t-parallel extension of
M
, is a disjoint union of
s
bases of
M
.
Lemma 2.4 ([14], [1] and [2]) Let
M
be a matroid
with ()>0rM , and let 1l be fractional number.
Each of the following holds.
1) (Lemma 10 [14]) If ()
X
EM and if
(|) ()
M
XM

 , then (/)=()
M
XM

 .
2) (Theorem 17 of [14]) If ()
X
EM and if
()=()dX M

, then
(|)= (|)=()= ()
M
XMXdXM

 .
3) A matroid
M
is uniformly dense if and only if
any subset ()
X
EM, ()( )dX M

.
4) A matroid
M
is uniformly dense if and only if for
any restriction N of
M
, ()( )NM

 .
5) If ()dM l, then there exists a subset
()
X
EM with ()>0rX such that (|)
M
Xl

.
For each rational number >1l, define
 
=:.
l
SM Ml   (6)
Proposition 2.5 ([1] and [2]) Let >>0pq be inte-
gers, and =p lQ
q
 be a rational number. The ma-
troid family l S satisfies the following properties.
(C1) If ()=0rM , then l
M
S

.
(C2) If l
M
S

and if ()eEM, then /l
M
eS

.
(C3) Let ()
X
EM and let =|NMX. If
/l
M
XS

and if l NS

, then l
M
S.
Lemma 2.6 ([1] and [2]) Let W, ()WEM
 be
subsets, and let lQ


. If (|)
M
Wl

 and
(|)
M
Wl


, then (|( ))
M
WW l

 
.
Lemma 2.7 ([1] and [2 ]) If ()
X
EM is an

-
maximal subset, then
X
is a closed set in
M
.
3. Characterization of the Must-Added
Elements with Respect to Having k
Disjoint Bases
The main purpose of this section is to prove Theorems
1.4. We will start with a lemma.
Lemma 3.1 Let
M
be a matroid and let >0k be
an integer. Each of the following holds.
1) ()
M
k

 if and only if (,)=0FMk .
2) If ()
M
k


, then


,= .FMk krMEM
Moreover, there exists a map :( )EM N

, such
that
M

is a matroid that contains M as a restrict-
tion with()=()=
M
M
k


, and such that
|()||( )|=(,)EMEM FMk


.
Proof: 1) By (2), ()
M
k

 if and only if ()
M
k

.
By the definition of (,)
F
Mk, ()
M
k

 if and only if
(,)=0FMk . This proves 1).
2) Since ()
M
k


, it follows by (2) that
M
has
disjoint bases 1,,
k
BB such that =1 ()= k
i
i
EM B
.
Define ()=|{ :}|
ii
eBeB


. Then :( )EM N

. Let
=LM

be the

-parallel extension of
M
. Then by
Definition 2.1,
M
is contained in L as a restriction.
Moreover, both
 
=1
==
k
i
i
ELBkrM
and ()=Lk

.
It follows by Theorem 2.3 that ()= ()=LLk

. Hence
by Theorem 2.3 1) or 2), |E(L)| = k r(L) = k r(M), and so
(,)=|()||()|= ()|()|
F
Mk ELEMkrMEM

.
When =2k, the cycle matroid version of Lemma 3.1
has been frequently applied in the study of supereulerian
graphs, see Theorem 7 of [18] and Lemma 2.3 of [19],
among others. (For a literature review on supereulerian
graphs, see [20] and [21].)
Proof of Theorem 1.4 1): Let
M
be a matroid with
()>0rM . If ()
M
k

, then by (2) and by Theorem
1.3, 1
()=ik i, and so
()
()= ,(,)=0.
ik
E MJandFMk
Thus Theorem 1.4 1) follows trivially with ()
M
k

.
Hence we assume that ()<
M
k

. If ()<
M
k

, then
Theorem 1.4 1) follows from Lemma 3.1.
Therefore, we may assume that ()<
M
k

and
()
M
k

. By Theorem 1.3, we must have>1m. Let

H.-J. LAI ET AL.
247
()ik be the smallest subscript in

-spectrum (3) of
M
such that ()ik lk. By Theorem 1.3,() (|)
ik
M
Jk

. Let
()
=/
ik
M
MJ
. By the assumption that ()<
M
k

and
by Lemma 2.4 1), ()=()
M
M

. By the choice of
()ik, ()<
M
k

, and so by Lemma 3.1,
 
,=||,FM kkrMEM

 (7)
and there must be a function :( )EM N


 such that
M


 satisfies ()=()=.
M
Mk




Define :

()EM N as follows:
 
()
()
=.
1
ik
ik
eifeJ
eif eJ


 




Then
M

is a matroid that contains
M
as a restric-
tion, such that ()( )
k
J
MEM

. By the definition of

,
() ()
|=|
ikik k
M
JMJS

. Since () /=
ik k
M
JMS




,
it follows by Proposition 2.5(C3) that k
M
S

. Thus
by (7) and by Lemma 2.7,
 




() ()
,= ,=
=,
ik ik
FMkFM kkrMEM
krM rJEMJ



and so Theorem 1.4 1) is established.
To continue our proof for Theorem 1.4, we introduce
the following function: for any ()
X
EM, define

 

()
,= ,
=,.
max
k
kk
XEM
fMX krMX MX
and FMfMX


(8)
The function (,)
k
f
MX was introduced by Bruno
and Weinberg [22] to investigate the principal partition
of matroids. They are closely related to the strength and
fractional arboricity of matroids, as to be shown in
Lemma 3.2 below.
Lemma 3.2 Let
M
be a matroid with ()>0rM ,
and let >0k be an integer. Each of the following
holds.
1) ()=0
k
FM if and only if ()
M
k

.
2) ()= (,)
kk
FMf M if and only if ()
M
k


.
3) Let ()ik denote the smallest
j
i in (3) such that
()ikk, and ()ik
J
denote the corresponding set in the

-decomposition (4) of
M
. Then
()
(/ )=(,)
kik
F
MJ FMk.
4) For any ()eEM, ()( /)
kk
F
MFMe. In par-
ticular, () (,)
k
F
MFMk.
5) If 0()
X
EM satisfies0 ()=(,)
kk
F
MfMX, then
000
()=(/)=(/)=(/,)
kkk k
FMfMXFMXfMX

and
0
(/)
M
Xk

.
Proof: 1) By definition (8), ()=0
k
FM if and only if
()
X
EM , (,)=(/)|(/)|0
k
fMX krMXEMX.
By the definition of ()
M

, ()
X
EM

,
(/)|(/)|0krM XEM X if and only if ()
M
k

.
2) By the definition of ()
k
F
M, ()= (,)
kk
FMf M

if and only if ()
X
EM

,
(( )())||()| |;krMrXEXkrME


and so if and only if ()
X
EM

 with ()>0rX ,
||
()
Xk
rX

. By the definition of ()
M

, this happens if
and only if ()
M
k


.
3) By Theorem 1.3, ()
(/ )<
ik
M
Jk

. By 2) of this
lemma, by Lemma 2.7, and by Theorem 1.4 1),




 
 

()()() ()
() ()
=,=
==,.
kik kikikik
ik ik
F MJfMJkrMJMJ
krMrJE JFMk


4) For any ()eEM

, by the definition of ()
k
F
M in
(8), ()(/)
kk
F
MFMe. It follows by 3) of this lemma
that ()(,)=(,)
kk
F
MfMXFMk.
5) By 4), and by the choice of0
X
, we have




 
00
0
,
=,= .
kk k
kk
FMFMXf MX
fMX FM

Thus equalities must hold and so
000
()=(/)=(/)=(/,)
kkk k
FMfMXFMXfMX

..It
follows by 2) that0 (/)
M
Xk

. This proves 5).
Lemma 3.3 Suppose that 0()
X
EMsatisfies
0
(,)= ()
kk
f
MXF M. Then 0 (| )
M
Xk

.
Proof: By Lemma 3.1 1), it suffices to show that
0
(| )=0
k
FMX . For any 0 YX, as



 


  


00 0
000
|,= ,
,= .
k
k
f MXYkrXrYXY
andfM Xk r MrXE MX


It follows that 00 (|,)(, )=(,)
kkk
f
MXY fMXfMY
0
()=(,)
kk
F
MfMX. Thus by definition, 0 (| ,)0
k
f MXY

.
This implies that0
(| )=0
k
FMX , and so0 (| )
M
Xk

.
Proof of Theorem 1.4 2): By Lemma 3.2 4), it suf-
fices to show that () (,)
k
F
MFMk

. We shall argue by
induction on |()|EM to proceed the proof.
Suppose first that ()=0
k
FM . Then by Lemma 3.2 1),
()=0
k
FM if and only if ()
M
k

. By Lemma 3.1 1),
we have (,)=0= ()
k
F
MkF M in this case. Thus we
assume that ()>0
k
FM .
By Lemma 3.1 1), ()>0
k
FM if and only if
()<
M
k

. If ()
M
k


, then by Lemma 3.1 2), and by
Lemma 3.2 2),






=,= =,.
kk
F
MfM krMEMFMk
Hence we may assume that Theorem 1.4 2) holds for
smaller values of |()|EM , and that
()<<().
M
kM

(9)
By induction, we may assume that
M
does not have
loops. By Theorem 1.3, and by (9), both ()ik, the smal-

H.-J. LAI ET AL.
248
lest j in (3) such that j
lk, and ()ik
J
, the corre-
sponding set in (4), exist.
Let 0()XEM be a subset such that 0 ()=(,)
kk
F
MfMX
.
By (9), 0 X . Since 0 |(/)|<|()|EM XEM, by
Lemma 3.2 5) and by induction, we have
 

000
0
===,,
.
kk k
F
MfMX FMX FMXk
andM Xk
 
Suppose that (,)=
F
Mk l. Then there exists a ma-
troid
M
 with k
M
S
, which contains
M
as a res-
triction and satisfies |()( )|=EM EM l

. Note that
0()( )
X
EM EM

 . Let =()()WEM EM
, and
00
=()
M
WWclX

. Then 0 ||||WW.
Since k
M
S , it follows by Proposition 2.5 (C2)
that 0 /k
M
XS . Since
M
is a restriction of
M

,
0
/
M
X is a restriction of 0 /
M
X . It follows by the
definition of 0 (/ ,)
F
MXk and by (10) that
 



000
0
=,
=,.
k
F
MFMXkEMXEMX
WWFMk



This, together with Lemma 3.2 4), implies Theorem 1.4
2).
4. Applications
Let G be a graph, and =()
M
MG be the cycle ma-
troid of G. Let(,)=( (),)
F
GkFMGk, and
(, )=((), )
kk
fGX fMGX, for any edge subset
X

()EG . Let ()G

denote the number of connected
components of G. The next theorem follows immedi-
ately from Theorem 1.4.
Theorem 4.1 (Theorems 3.4 and 3.10 of [4]) For
kN, let G be a connected graph with (())
M
Gk


and let ()ik denote the smallest
j
i in (3) such that
()ikk. Then
1) () ()
(,)=(| ()|| ([])|([])
ik ik
FGkk VGVGJGJ


()
1) |()|
ik
EG J.
2) ()
(,)={ (,)}
max XEG k
F
Gkf GX
.
The problem of reinforcing graphs to have k edge-
disjoint spanning trees has also been investigated by oth-
ers. In [3], the following is proved.
Theorem 4.2 (Haas, Theorem 1 of [3]) The following
are equivalent for a graph G, and integers >0k and
>0l.
1) |()|=(|()|1)EGk VGl and for subgraphs
H
of G with at least 2 vertices, |()| (|()|1)EHk VH.
2) There exists some l edges which when added to
G result in a graph that can be decomposed into k
spanning trees.
Proof: Assume that 1) holds. Then by 1),
(())
M
Gk

. It follows by the assumption that
|()|=(|()|1)EGk VGl and by Lemma 3.1 2) that
(,)=
F
Gk l, and so 1) is obtained.
Assume 2) holds. Since adding l edges to G can result
in a graph in k
S, by (1) and by (2), (())
M
Gk


. By
Lemma 3.1 2),



 
1=,=,kVGEGFGk l
and so 2) must hold.
5. References
[1] H.-J. Lai, P. Li and Y. Liang, “Characterization of Re-
movable Elements with Respect to Having k Disjoint
Bases in a Matroid,” Submitted.
[2] P. Li, Ph.D. Dissertation, West Virginia University, to be
Completed in 2012.
[3] R. Haas, “Characterizations of Arboricity of Graphs,” Ars
Combinatoria, Vol. 63, 2002, pp. 129-137.
[4] D. Liu, H.-J. Lai and Z.-H. Chen, “Reinforcing the Num-
ber of Disjoint Spanning Trees,” Ars Combinatoria, Vol.
93, 2009, pp. 113-127.
[5] D. J. A. Welsh, “Matroid Theory,” Academic Press,
London, New York, 1976.
[6] J. G. Oxley, “Matroid Theory,” Oxford University Press,
New York, 1992.
[7] J. A. Bondy and U. S. R. Murty, “Graph Theorym,”
Springer, New York, 2008.
[8] E. M. Palmer, “On the Spannig Tree Packing Number of
a Graph, a Survey,” Discrete Mathematics, Vol. 230, No.
1-3, 2001, pp. 13-21.
[9] C. St. J. A. Nash-Williams, “Edge-Disjoint Spanning
Trees of Finite Graphs,” Journal of the London Mathe-
matical Society, Vol. 36, No. 1, 1961, pp. 445-450.
[10] W. T. Tutte, “On the Problem of Decomposing a Graph
into n Connected Factors,” Journal of the London Ma-
thematical Society, Vol. 36, No. 1, 1961, pp. 221-230.
[11] J. Edmonds, “Lehman’s Switching Game and a Theorem
of Tutte and Nash-Williams,” Journal of Research of the
National Bureau of Standards, Section B, Vol. 69B, 1965,
pp. 73-77.
[12] C. St. J. A. Nash-Williams, “Decomposition of Fininte
Graphs into Forest,” Journal of the London Mathematical
Society, Vol. 39, No. 1, 1964, p. 12.
[13] W. H. Cunningham, “Optimal Attack and Reinforcement
of a Network,” Journal of Associated Computer Macha-
nism, Vol. 32, 1985, pp. 549-561.
[14] P. A. Catlin, J. W. Grossman, A. M. Hobbs and H.-J. Lai,
“Fractional Arboricity, Strength and Principal Partitions
in Graphs and Matroids,” Discrete Applied Mathematics,
Vol. 40, No. 1, 1992, pp. 285-302.
[15] A. M. Hobbs, “Computing Edge-Toughness and Frac-
tional Arboricity,” Contemporary Mathematics, Vol. 89
1989, pp. 89-106.
[16] A. M. Hobbs, L. Kannan, H.-J. Lai and H. Y. Lai,

H.-J. LAI ET AL.
249
“Transforming a Graph into a 1-Balanced Graph,” Dis-
crete Applied Mathematics, Vol. 157, No. 1, 2009, pp.
300-308.
[17] A. M. Hobbs, L. Kannan, H.-J. Lai, H. Y. Lai and Q. W.
Guo, “Balanced and 1-Balanced Graph Construction,”
Discrete Applied Mathematics, Accepted.
[18] P. A. Catlin, “Super-Eulerian Graphscollapsible Graphs,
and Four-Cycles,” Congressus Numerantium, Vol. 58,
1987, pp. 233-246.
[19] P. A. Catlin, Z. Han and H.-J. Lai, “Graphs without
Spanning Closed Trails,” Discrete Mathematics, Vol. 160,
No. 1-3, 1996, pp. 81-91.
[20] P. A. Catlin, “Super-Eulerian Graphs - A Survey,” Jour-
nal of Graph Theory, Vol. 16, No. 2, 1992, pp. 177-196.
[21] Z. H. Chen and H.-J. Lai, “Reduction Techniques for
Super-Eulerian Graphs and Related Topics - A Survey,”
Combinatorics and Graph Theory 95, Vol. 1, World Sci-
ence Publishing, River Edge, New York, 1995.
[22] J. Bruno and L. Weinberg, “The Principal Minors of a
Matroid,” Linear Algebra and Its Applications, Vol. 4,
1971, pp. 17-54.