Open Journal of Discrete Mathematics, 2012, 2, 125-130
http://dx.doi.org/10.4236/ojdm.2012.24024 Published Online October 2012 (http://www.SciRP.org/journal/ojdm)
4-Cycle Decompositions of Graphs
Teresa Sousa
Departamento de Matemática and Centro de Matemática e Aplicações,
Faculdade de Ciências e Tecnologia, Universidade Nova de Lisboa, Lisbon, Portugal
Email: tmjs@fct.unl.pt
Received May 10, 2012; revised June 3, 2012; accepted August 6, 2012
ABSTRACT
In this paper we consider the problem of finding the smallest number
such that any graph G of order n admits a de-
composition into edge disjoint copies of C4 and single edges with at most
elements. We solve this problem for n
sufficiently large.
Keywords: Graph Decomposition; 4-Cycle Packing; Graph Packing
1. Introduction
All graphs in this paper are finite, undirected and simple.
For notation and terminology not discussed here the
reader is referred to [1].
Given two graphs and
G
H
, an
of is a partition of the edge set of such that each
part is either a single edge or forms an , i.e.,
a graph isomorphic to
-decompositionH
G
-subgraphH
G
H
. We allow partitions only, that
is, every edge of appears in precisely one part. Let
be the smallest possible number of parts in an
of G. For non-empty
G
G
-dec
H
omHposition
H
, let
be the maximum number of pairwise edge-
disjoint that can be packed into G and
the number of edges in . It is easy to see that
p

eG
HG
-subgrHaph
G
  
1.
HH
GeGpGeH
 
(1.1)
Here we study the function


max ,
HH
nGvG

n
which is the smallest number, such that, any graph
of order admits an with at most
elements.
G
n-decompositionH

Hn
The function
H was first studied by Erdös,
Goodman and Pósa [2], who proved that
n

2
ntn
3
K,
where r
K
denotes the complete graph (clique) of order
and is the maximum size of an r-partite graph
on vertices. A decade later, this result was extended
by Bollobás [3], who proved that
r
r
t
n
n
 
1,forall 3.
Kr
rnt nnr

Recently, Pikhurko and Sousa [4] studied
Hn
for
arbitrary graphs
H
.
be
any fixed graph of chromatic number 3r. Then,

nt non

2.
Theorem 1.1. (See Theorem 1.1 from [4]) Let
H
1Hr
ex ,nH
aph of or
Let denote the maximuber of edges
in
m num
a grder n, that does not contain
H
as a
subgraph. Recall that

1
ex, rr
nKt n
. Pikhuro and
Sousa [4] also made there.
Conjecture 1. For any graph
k
following conjectu
H
with chromatic
number at least 3, there is

00
nnH such that
ex ,
HnnH
, for all 0
nn
of the function
.
The exact value

Hn
few
is far from
be
wing
) Let
ing known. Sousa determined it for a special edge-
critical graphs, namely for clique-extensions of order
4r (nr) [5] and the cycles of length 5 (6n) and
10 ,7]. Later, Özkahya and Person eter-
mined it for all edge-critical graphs with chromatic num-
ber 3r and n sufficiently large. They proved the
follo result.
Theorem 1.2. ([8]
7 (n) [6[8] d
H
r
be any edge-critical graph
with chromatic number 3. Then, there exists 0
n
such that
,
g
ex ,
HnnH
or all 0
nn. Moreove
the only graph
fr,
attainin
Hn
is thurán graph e T
1r
Tn
.
Recently, Allen, Böttcher and Person [9] improve
err
e case when
d the
or term obtained by Pikhurko and Sousa in Theorem
1.1.
Th
H
nd
is a bipartite gas been less
st
raph h
udied. Pikhurko a Sousa [4] determined
Hn
for
any fixed bipartite graph with an

1O addrror.
For a non-empty graph
itive e
H
, let

gcd
H
denote the
greatest common divisor the of H. For
example,
of degrees
6,4
gcd 2K
while for any tree T with at
least 2 vee

gcd 1T. They ped the
following result.
rtices we vharov
C
opyright © 2012 SciRes. OJDM
T. SOUSA
126
Theorem 1.3. (See Theorem 1.3 from [4]) Let
H
be
a bipartite graph with m edges and let
gcdH.
Then there is

00
nnH such that for all e
following statem
d
0
nn th
ents hold.
 
1
2
H
nn
nC
m




(1) If 1d, then , where
.
(2) If , then
1Cm or 2Cm
2d
 
1
11
22
H
nd
1dO
md





 .
Moreover, there is a procedure running in polynomial
in
e
n
nn

log n time which determines

Hn
and describes
a f of n-sequences suc a graph G of
order nsatisfi
 
HH
Gn

if and only if the
degree sequence of . (It will be the
case that
amily
h that
to
s
G belongs

1Oand each seqnce in has

1nO equal entries, so can be describedsing
bits.)
e will det
rmine the exact val
ue
ue
u
logO
Here w
of
n
e
n
4
C
for
is such that for all
(1) If
n sufficiently large.
Theorem 1.4. There

004
nnC
ents hold.
0
n the following statem
n is even then

n
4
2
n
n
1.
84
C
n
(2) If then

1mod8n

4
214 .
888
C
nn
n

(3) If then

3mod8n

4
23.
882
C
nn
n

(4) If then

5mod8n

4
210 .
888
C
nn
n

(5) If then

7mod8n

4
2
2.
88
C
nn
n

eorem 1.4, but first we
2. Proof of Theorem 1.4
In this section we will prove Th
need to introduce the tools. We start with the following
easy result about
H
-decompositions.
Lemma 5. (Lema 1.3) For any nonm-empty graph
H
with m edges and any integer n, we have
 
11
ex ,.
2
H
nm

nnH
mm


 (2.1)
In particular, if
H
is a fixed bipartite graph with
ed
m
ges and n, then
 
11.
2
H
n
nO
m


 



(2.2)
The following result is the well known Erdös-Gallai
th
6. (Erdős-Gallai Theorem [10]) Let
eorem that gives a necessary and sufficient condition
for a finite sequence to be the degree sequence of a
simple graph.
Theorem 2.
1n
dd0
 be a sequence of integers. There
ee sequence 1,,
n
dd if and only if
(1) 1n
dd
is a
graph with degr
is even;
(2) fkn
or each 1


11
1min,
nnk
ii
ink i
dkkdk
 


.
(2.3)
The following results appearing in Alon, Caro and
Y
-empty graph
uster [11, Theorem 1.1, Corollary 3.4, Lemma 3.5]
which follow with some extra work from the powerful
decomposition theorem of Gustavsson [12] are essential
to the proof of Theorem 1.4.
Lemma 2.7. For any non
H
with
ed
m
ges, there are >0
and 0
N such that tfollowin
holds. Let
he g
um
gcddHet G graph of order
0
nN and of minim

1Gn
. Lbe a
degree
.
If d
1
, then
 
.
H
eG
pG m
(2.4)
If , let
2d

deg
u
u
dd
for
uVG and
let
X
cons
b
ist of e degrdivi-
sibly d. If
all vertices whosee is not
e 3
10
Xd
, then
n


1.
2
Hu
uVG
pG m
(2.5)
If 3
<10
n
Xd, then
 
2
1.
5
H
n
pG eG
md




(2.6)
One can extract the following result from the proof of
Theorem 1.2 from [
4].
Lemma 2.8. Let H be a bipartite graph with m
edges and let
gcd H2d
. Then, there is
00
nH such that if G is a graph of orde0
nn
with
r
G
d
n
H
hen the following
H
1,,
n
d be the degree sequence of G
nt holds:
(1) Let , then
 
11
11
1.
22
ii
G


(2) Let
nn
i
Hi
d
dm d
md





(2.7)
nqdr
i
r
with and 0 1rd
ii
dqd
with 01rd
i
. Then, for 1in
exactly onlowing ho
1
id
e of the follds:
dq
(a) ;
(b)
1
i
d qd
11and
i
iCinrd
;
(c)
21
i
iCi ndn
  if and 1nR
Copyright © 2012 SciRes. OJDM
T. SOUSA 127
2C otherwise.
hermore, Furt1
21
m
Cd

and 221Cm
.
following we

briefly sketch the proof of Lemma
e argument . We refrom
ulations.
In the
2.8
do
by giving thform [4]ain fr
ing all the calc
Sketch of the proof of Lemma 2.8. Let
4
C
and
0
N be given by Lemma 2.7. Assume that
is
sufficiently small and that is sufficiently large
to 00
nN
satisfy all the inequalities we will enco Let
0
n and let G be any graph of order n with
 
44
CC
Gn

.
Let n
GG. Repeat the following at most
unter.
n
lognn
If the crrent graph i
G has a ertex i
times: uv
x
of
degree at most
12
i
i
ande- , let 1ii
GGx
 d
cre i
ase
Suppose we stopped after
by 1.
s
repetitions. Then, either

12
ns
G

 or

n slog
s
nn


. L
r cannot happen. Otherwise, we have
et us
show tht the latea

2
n
ns n


1
22
1.
n
(2.8
2
i


 
 
 4
log
ins n


eG
Let t
 )
satisfy

,tt
K
H. Using the fact that


21t
n
,
ex ,nK
tt O, (2.1) and (2.8) we obtain


2
21
11
t
H
nm
Gcn
 
24l
ogn
m
1,
2Hn
n
m
nK
m






ontradicts our assumption on . Therefore, which cG
log
s
nn

and we have

12
ns
Gn

 . s
Let 2
, We will have anor pass over the
mes
incident
the
vertices 1
,,
nns
xx

, each time decoposing the edg
i
to
x
by
H
-subgIt raphs and single edges.
will be the ca
o the c
se that each time we remove the edges
incident tt vertex i
urren
x
, the degree of any other
vertex drops at m 4
3h, where

hvH. Here is
a formal description. Initially, let n
GG
and in
by ost
. If
in the current graph i
G we ha e

deg i
Gi
v
x
n
, then
we remove all i
G-edges incident to i
x
as single edges
and let 1iii
GGx

.
Suppose that
deg ii
G
x
n
. Then, the set
 

V,
insii
Xy GxyEG

has at least n1s
 The minimum d vertices.egree of
i
GX is


42
3.
23
i i
GX sshX

i
n
X

Let

y
VH,

H
A
y and aA. Another
result from [4] (Lemma 3.1) states that there is a constant
, such that, all but at most vertices of
CC
i
GX can
red by eddisjointbe covege pies of co
H
y each of
them having vertex disjoint sets
A
. Therefore, all but at
most C edges between i
x
and i
X
can be decom-
posed into copies of
H
. All other edges inc i
ident to
x
are removed as single edges. Let 1i
G
consist of the
remaining edges of ii
Gx
(that is, those edges that do
not belong to an
H
-subgraph of the above i
x
-
decomposition). This finishes the description of the case
deg ii
G
x
n
.
Consider the sets
1
,,
nns
Sxx

,

1deg
ii
G
SxSx n
i
 , and 21
SSS. Let their
sizes be
s
, 1
s
, and 2
s
respectively, so 12
s
ss.
Le t
F
be the gret VG
ap
es co
h wit
m
h vert
i
ex s
th

m2ns
ng fromoved
S,
consisting of the edge re
H
-
subgraph wecessed the vertices in. W
have
when pro 2
Se
s


12 .
2
HHns
eF
s
GG snsC
m
 




()
We
2.9
know that
 

1m
Hns n
G


s H
p
ns
G
Ge
,
rtheore, furm

Gn

1
ns
s . Thus,
H
ns
G
p
can
gra
be estim
G
ated using Lemma 2.7.
If (2.6) holds, some calculations show that there exits a
such that

HH
GG
.
, which contra-
ph
dicts the optimality go
Therefore, (2.5) must hold. It follows that
G
G
H
p
and thus
G
, depends only on
Hthe degree sequence
1,,dd of G. Namely, the packing ber
n num
H
pG equals 1
2m
1n
i
ir
, where ii
rddd
There
is the largest multiple of d not exceeding i
d.
ore, f
 
11
ii
o
by
11
2
i
d
Gd md

1,
2
Hd

nn
i
m
can attain. To
H
e an



(2
e need t estim val
that the degrees of do that w
upper bouestimati


 .10)
ues
max
where ,,
n
dd is the degree sequence of G.
1
To conclude thproof we
G
nd on
ate the
e need to
ng prov

G
,
the ma ximum of


1
=1
11
,, =1,
22
nn
i
ni
ii
d
dd dmd
md








(2.11)
over all (not necessarily gra) sequences ,d
of integers with 0
=1
i
phical
11,
n
d
dn

opti
.
malLet sequence att
1
ma
,,
n
dd
x
be an aining the
value
. For 1, ,in
let ii
dqdr
i
with
01
i
rd
. Then,
1n
qqd
2m

.
Copyright © 2012 SciRes. OJDM
T. SOUSA
128
Let r with 01rd and nqd qnd
.
Define qd e maxi
1R
st 1n an
to be integer which is
at mo codulo
Let
thmum
ongruent to dd is m
1d.

1and <
ii
d
1dCi
nrR and

21n if and
i Cind 1nR2
C
otherwis
Since ,
n
dd is an optimal sequence, we have that
if i
r[]in.
e.
for all To con-
clude the proof it remao show th
1,
1d then 1
i
dn
ins tat 1
C21
m
d
an
d 221mC. Suppose first that 1
2=:
m
Ct
d
.
Consider the new sequence of integers
h contradicts
1i
i
d
1
,if,
,if.
i
dd iC
diC

Then, 1 and max 1

whic
our assumption on max
 
.
Now suppose that 22Cm and consider the new se-
quence of integers obtained
by replacing by
and
1,,
n
dd

values of
from1,,
n
dd
. Then,
2m1nR
d max max
md

, which contra-
dicts our assumptin
on omax

and the proof is con-
cluded.
We now have all theded to prove Theo.
Proof of Theo 1.4. Let 0
n ben by ma 2.8.
e a grap0
 
44
CC
Gn

and degrsequence 1,,
n
dd. For
1, ,in let 2dqr with 01r . Let,
e tools nerem 1.4
rem e givLem
Let bh of order with
ee
G nn
iiii

2211n

 and let the sets C and C be as R1 2
in Lemma 2.8.
Le 2nqr with 01and t r 2qn


. From
(2.7) we obtain





4
2
1
22
11
C
q 
(2.12)
2
1
1
11
1
31 1
444
C
i
i
i
iC
nCrq
nqCq q
 




In what follows let
n
nq 
2
C
and
We consider first the case when is even. Then
and we have

1
i
iC
qq

1.
n
2
C
 
 
4
1
13
Cnn
q nq1
24 4
2 4
n
31
13
2
qq
n
nq


 
(2.13)
 

 


Claim 1. Let be the degree sequence of a
graph. Then, 1,,
n
dd
31
4

.
 


Proof. Routine calculations show that for 1
we
have 31.

4
 

Suppose
1
nce
. Then has
lement, thus the seque has
exactly one element equal to and all the others
equal to
1
C
1, ,in
exactly one e

i
d
3n
1n
. But this is degree sequence of a
gr
fo
not a
aph since condition (2.3) of Theorem 2.6 does not hold
r 2kn
.
sing thelai .1
follows that
The estimate ofm 1 in (23) it refore, u C

41.
8
Cn
2
nn
4

To prove the lower bound consider the graph 5
L
obtai n
ned from
K
after the deletion of the edges of a
C
5. Using (1.1) and (2.5) we show that

4
2
51.
84
C
nn
L

We now consider the case when is an odd number.
n
Case 1: Let 81nt
and 4qt.
From (2.12) wobtain

e


4
2
nn
338
22
11
3
Cnn tt


24




(2.14)
the degree sequence of a
gr


Claim 2. Let . be
1n
aph. Then,
,,dd
11
3.
24




5
2



Proof. Routine calculations show that the result
follows if or 0
. If 0
and 0
then 0
2n
i
d
for anll 1i
n
. This is not a degree se-
quence of a gra1i
id
ph since is not even.
Therefore, using the estimate of Claim 2 in (2.14) we
prove that

4
214.
88
C
nn
n

the lower consider the graph L
8
As for bound
with
all vertices of degree n2
except one of degree n3
.
Using (1.1) and (2.5) we show that

4
214 .
888
C
nn
L

Case 2: Let 83nt
and
From (2.12) we obtain
41qt
.
Copyright © 2012 SciRes. OJDM
T. SOUSA 129
 

4
2
3383
22
1
C
nn
3.
24
nn




(2.15)
Claim 3. Let be the degree sequence of a
gr
tt
 
1,,.
n
dd
aph. Then,
13
3.
242






Proof. It follows from routine calculatio
values of
ns for all
and
except when 0
and 1
.
Suppose that 0
and 1
. Th
ha element,
en 2
C and 1
C
s exactly one thus the sequence
1, ,
iin
d
has exactly one element equal to and all the
others equal to . But this is notee sequence
of a graph since is not even.
ore, usi estimate of Claim 3 in (2.15)
pr
2n
a degr1n
i
d
ng the
we Theref
ove that

488
2
C
23.
n
n
n
he gAs for the lower bound consider traph L with
degree sequence24d n, 31
2
n
ddn
 
1
d
(the and 1
n
dn existence of L can be proved
directly or by Erdös-Gallai theorem, Theorem 2.6). Using
(1.1) and (2.5) we show that

4
23.
882
C
nn
L

Case 3: Let 85nt and 42qt
.
From (2.12) we o

btain


4
2
3387
22
1
C
nn
5
3.
24
nn







(2.16)
Claim 4. Let be the degree sequence of a
gr
tt
 
1,,.
n
dd
aph. Then,
1

55
3.
242



 


Proof. Routine calculations show that
5
23 5
4




 


2
for all values of
and
β except for 2
=0 and
or =0
and =2
.
Suppose first that 2
and =0
. Then t
quence has to
he se-

1, ,
iin
d wo elements equal t1n
and
all the others equal to . Thiee se-
quence osince even.
2n
n
s is not a
is not
degr
f a graph 1i
i
Suppose now that =0
d
and =2
. If 1
C2
then the sequence hasmo and
all the others equal to 2n
nce
two eleents equal t4n
and this is not a degree
is not even. Finly, if sequence of a graph sial
i
d
11C
thenave one element equal to n we h6
and
all the others equal to 2n
. Again, this is not a degree
sequencegraph since i
d
of a
is not even.
Therefore, using the ete of Claim 4 in (2.16) we
prove that
stima

4
1.
888
Cn

As for the lower boundsider the graph n
2
nn
con
0
K
I
obtained from n
K
by deleting the edges of a mum
matching. Using (1.1) a.5) we show that
maxi
nd (2

4.
888
Cn
KI
 
Case 4: Let
210nn
87nt
and
tain
43qt.
From (2.12) we ob
 

4
2
33811
22
114
3.
24
C
nn
nn
Claim 5. Let be the degree
graph. Then,
tt


 





(2.17)
1,,.
n
dd sequence of a
1
3
24



14

Proof. It follows directly from simple calculations.
Therefore, using the estimate of Claim 5 in
prove that
17

 .
2
(2.17) we

4
2
2.
88
C
nn
n

Furthermore, using (1.1) and (2.5) we have

4
2
2,
88
Cn
nn
KI

so
ledgements
The author would like to thank Oleg Pikhurk
co
su T
nologia (Portugal), through Projects PTD2
2009 and PEst-OE/MAT/UI0297/2011 (CA)
REFERENCES
aph Theory,” Spring
the equality follows and the proof is now complete.
3. Acknow
o for help
ge
e a
AT/11 3
.
er-Verlag
ful
s the
ec-
07/
,
mments and discussions. The author acknowled
pport from FCT—Fundação para a Ciência
C/M
M
[1] B. Bollobás, “Modern Gr
New York, 1998. doi:10.1007/978-1-4612-0619-4
[2] P. Erdös, A. W. Goodman and L. Pósa, “The Representa-
tion of a Graph by Set Intersections,” Canadian Journal
Copyright © 2012 SciRes. OJDM
T. SOUSA
Copyright © 2012 SciRes. OJDM
130
of Mathematics, Vol. 18, No. 1, 1966, pp. 106-112.
doi:10.4153/CJM-1966-014-3
[3] B. Bollobás, “On Complete Subgraphs of Different Or-
ders,” Matheme Cambridge Phi-
losophical Soc6, pp. 19-24.
atical Proceedings of th
iety, Vol. 79, No. 1, 197
doi:10.1017/S0305004100052063
[4] O. Pikhurko and T. Sousa, “Minimum H-Decompositions
of Graphs,” Journal of Combinatorial Theory Series B,
Vol. 97, No. 6, 2007, pp. 1041-1055.
doi:10.1016/j.jctb.2007.03.002
[5] T. Sousa, “Decompositions of Graphs into a Given Clique-
, “Minimum H-Decompositions
Extension,” ARS. Combinatoria, Vol. 100, 2011, pp. 465-
472.
[6] T. Sousa, “Decompositions of Graphs into 5-Cycles and
Other Small Graphs,” Electronic Journal of Combina-
torics, Vol. 12, 2005, 7p.
[7] T. Sousa, “Decompositions of Graphs into Cycles of
Length Seven and Single Edges,” ARS. Combinatoria, to
appear.
[8] L. Özkahya and Y. Person
of Graphs: Edge-Critical Case,” Journal of Combinatorial
Theory Series B, Vol. 102, No. 102, 2012, pp. 715-725.
doi:10.1016/j.jctb.2011.10.004
[9] P. Allen, J. Böttcher and Y. Person, “An Improved Error
Term for Minimum H-Decompositions of Graphs,” arXiv:
1109.2571v1, 2011.
[10] P. Erdös and T. Gallai, “Graphs with Prescribed Degree
d R. Yuster, “Packing and Covering
of Vertices,” Matematikai Lapok, Vol. 11, 1960, pp. 264-
274.
[11] N. Alon, Y. Caro an
Dense Graphs,” Journal of Combinatorial Designs, Vol.
6, No. 6, 1998, pp. 451-472.
doi:10.1002/(SICI)1520-6610(1998)6:6<451::AID-JCD6
>3.0.CO;2-E
[12] T. Gustavsson, “Decompositions of Large Graphs and
Digraphs with High Minimum Degree,” Ph.D. Thesis,
University of Stockholm, Stockholm, 1991.