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 , 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 non-empty 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 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 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 . 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 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 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 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 , 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 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 -decompositions. Lemma 5. (Lema 1.3) For any nonm-empty 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ö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 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 G-edges 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ö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 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 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.
|