Open Journal of Discrete Mathematics, 2012, 2, 125130 http://dx.doi.org/10.4236/ojdm.2012.24024 Published Online October 2012 (http://www.SciRP.org/journal/ojdm) 4Cycle 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; 4Cycle 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 , 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 . 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 nonempty G G dec H omHposition , 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 ndecompositionH 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 denotes the complete graph (clique) of order and is the maximum size of an rpartite 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 . be any fixed graph of chromatic number 3r. Then, nt non 2. Theorem 1.1. (See Theorem 1.1 from [4]) Let 1Hr ex ,nH aph of or Let denote the maximuber of edges in m num a grder n, that does not contain 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 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 cliqueextensions of order 4r (nr) [5] and the cycles of length 5 (6n) and 10 ,7]. Later, Özkahya and Person eter mined it for all edgecritical graphs with chromatic num ber 3r and n sufficiently large. They proved the follo result. Theorem 1.2. ([8] 7 (n) [6[8] d r be any edgecritical 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 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 nonempty graph itive e , let gcd 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 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 nsequences 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 decompositions. Lemma 5. (Lema 1.3) For any nonmempty graph with m edges and any integer n, we have 11 ex ,. 2 H nm nnH mm (2.1) In particular, if 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ösGallai th 6. (ErdősGallai 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 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 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 2C 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 of degree at most 12 i i ande , let 1ii GGx d cre i ase Suppose we stopped after by 1. repetitions. Then, either 12 ns G or n slog 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 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 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 by 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 , 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 n , then we remove all i Gedges incident to i as single edges and let 1iii GGx . Suppose that deg ii G 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 VH, H 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 y each of them having vertex disjoint sets . Therefore, all but at most C edges between i and i can be decom posed into copies of . All other edges inc i ident to 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 subgraph of the above i  decomposition). This finishes the description of the case deg ii G n . Consider the sets 1 ,, nns Sxx , 1deg ii G SxSx n i , and 21 SSS. Let their sizes be , 1 , and 2 respectively, so 12 ss. Le t 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  subgraph wecessed the vertices in. W have when pro 2 Se s 12 . 2 HHns eF 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, 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 1nR2 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 221mC. 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 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ösGallai 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 I obtained from n 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 PEstOE/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 . erVerlag 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/9781461206194 [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. 106112. doi:10.4153/CJM19660143 [3] B. Bollobás, “On Complete Subgraphs of Different Or ders,” Matheme Cambridge Phi losophical Soc6, pp. 1924. atical Proceedings of th iety, Vol. 79, No. 1, 197 doi:10.1017/S0305004100052063 [4] O. Pikhurko and T. Sousa, “Minimum HDecompositions of Graphs,” Journal of Combinatorial Theory Series B, Vol. 97, No. 6, 2007, pp. 10411055. doi:10.1016/j.jctb.2007.03.002 [5] T. Sousa, “Decompositions of Graphs into a Given Clique , “Minimum HDecompositions Extension,” ARS. Combinatoria, Vol. 100, 2011, pp. 465 472. [6] T. Sousa, “Decompositions of Graphs into 5Cycles 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: EdgeCritical Case,” Journal of Combinatorial Theory Series B, Vol. 102, No. 102, 2012, pp. 715725. doi:10.1016/j.jctb.2011.10.004 [9] P. Allen, J. Böttcher and Y. Person, “An Improved Error Term for Minimum HDecompositions 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. 451472. doi:10.1002/(SICI)15206610(1998)6:6<451::AIDJCD6 >3.0.CO;2E [12] T. Gustavsson, “Decompositions of Large Graphs and Digraphs with High Minimum Degree,” Ph.D. Thesis, University of Stockholm, Stockholm, 1991.
