### Journal Menu >> 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 . Given two graphs and GH, 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 -decompositionHG-subgraphHGH. 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omHpositionH, 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-subgrHaphG  1.HHGeGpGeH  (1.1) Here we study the function max ,HHnGvGn which is the smallest number, such that, any graph of order admits an with at most elements. Gn-decompositionHHnThe function H was first studied by Erdös, Goodman and Pósa , who proved that n2ntn3K, where rK 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 , who proved that rrtnn 1,forall 3.Krrnt nnr Recently, Pikhurko and Sousa  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 ) Let H1Hrex ,nH aph of orLet denote the maximuber of edges inm num a grder n, that does not contain H as a subgraph. Recall that 1ex, rrnKt n. Pikhuro and Sousa  also made there. Conjecture 1. For any graph k following conjectuH with chromatic number at least 3, there is 00nnH such that ex ,HnnH, for all 0nn of the function . The exact valueHnfew is far from bewing) Let ing known. Sousa determined it for a special edge- critical graphs, namely for clique-extensions of order 4r (nr)  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. (7 (n) [6 dH rbe any edge-critical graph with chromatic number 3. Then, there exists 0n such that ,g ex ,HnnHor all 0nn. Moreove the only graph fr, attaininHn is thurán graph e T1rTn. Recently, Allen, Böttcher and Person  improveerre case whend the or term obtained by Pikhurko and Sousa in Theorem 1.1. Th H ndis a bipartite gas been less straph hudied. Pikhurko a Sousa  determined Hn for any fixed bipartite graph with an 1O addrror. For a non-empty graph itive eH, let gcdH denote the greatest common divisor the of H. For example, of degrees6,4gcd 2K while for any tree T with at least 2 vee gcd 1T. They ped the following result. rtices we vharovCopyright © 2012 SciRes. OJDM T. SOUSA 126 Theorem 1.3. (See Theorem 1.3 from ) Let H be a bipartite graph with m edges and let gcdH. Then there is 00nnH such that for all e following statemd0nn thents hold.  12HnnnCm(1) If 1d, then , where . (2) If , then 1Cm or 2Cm2d 11122Hnd1dOmd . Moreover, there is a procedure running in polynomial in ennnlog n time which determines Hn and describes a f  of n-sequences suc a graph G of order nsatisfi  HHGn if and only if the degree sequence of . (It will be the case that amily h thattos G belongs 1Oand each seqnce in  has 1nO equal entries, so  can be describedsing bits.) e will det rmine the exact valueue ulogOHere wof nen4C for is such that for all (1) Ifn sufficiently large. Theorem 1.4. There004nnC ents hold. 0n the following statem n is even then n42nn1.84Cn (2) If then 1mod8n4214 .888Cnnn (3) If then 3mod8n423.882Cnnn (4) If then 5mod8n4210 .888Cnnn (5) If then 7mod8n422.88Cnnn eorem 1.4, but first we 2. Proof of Theorem 1.4In this section we will prove Thneed 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  11ex ,.2Hnm nnHmm (2.1) In particular, if H is a fixed bipartite graph with edm ges and n, then  11.2HnnOm  (2.2) The following result is the well known Erdös-Gallai th6. (Erdős-Gallai Theorem ) Let eorem that gives a necessary and sufficient condition for a finite sequence to be the degree sequence of a simple graph. Theorem 2.1ndd0 be a sequence of integers. Thereee sequence 1,,ndd if and only if (1) 1ndd is a graph with degr is even; (2) fknor each 1 111min,nnkiiink idkkdk . (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  are essential to the proof of Theorem 1.4. Lemma 2.7. For any nonH withed m ges, there are >0 and 0N such that tfollowin holds. Let he gumgcddHet G graph of order 0nN and of minim1Gn. Lbe a degree . If d1, then  .HeGpG m (2.4) If , let 2ddeguudd for uVG and let X consbist of e degrdivi- sibly d. If all vertices whosee is not e 310Xd, then n1.2HuuVGpG m (2.5) If 3<10nXd, then  21.5HnpG eGmd (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 00nH such that if G is a graph of orde0nn with r G dnHhen the followingH1,,nd be the degree sequence of G nt holds: (1) Let , then  11111.22iiG(2) Let nniHiddm dmd (2.7) nqdrir with and 0 1rdiidqd with 01rdi. Then, for 1in exactly onlowing ho1ide of the follds: dq(a) ; (b) 1id qd11andiiCinrd; (c) 21iiCi ndn  if and 1nRCopyright © 2012 SciRes. OJDM T. SOUSA 1272C otherwise. hermore, Furt121mCd and 221Cm. following we briefly sketch the proof of Lemma e argument . We refrom ulations. In the2.8 doby giving thform ain fring all the calcSketch of the proof of Lemma 2.8. Let 4C and 0N be given by Lemma 2.7. Assume that  is sufficiently small and that is sufficiently large to 00nN satisfy all the inequalities we will enco Let 0n and let G be any graph of order n with  44CCGn. Let nGG. Repeat the following at most unter.nlognn If the crrent graph iG has a ertex itimes: uvx of degree at most 12ii ande- , let 1iiGGx d cre iase Suppose we stopped after by 1.s repetitions. Then, either 12nsG or n slogsnn. Lr cannot happen. Otherwise, we have et us show tht the latea2nns n1221.n (2.82i   4logins neGLet t ) satisfy ,ttKH. Using the fact that 21tn,ex ,nKtt O, (2.1) and (2.8) we obtain 22111tHnmGcn 24lognm 1,2HnnmnKmontradicts our assumption on . Therefore, which cGlogsnn and we have 12nsGn . sLet 2, We will have anor pass over the mes incidentthevertices 1,,nnsxx, each time decoposing the edgi to x by H-subgIt raphs and single edges. will be the cao the cse that each time we remove the edges incident tt vertex iurrenx, the degree of any other vertex drops at m 43h, where hvH. Here is a formal description. Initially, let nGG and inby ost. If in the current graph iG we ha e deg iGivxn, then we remove all iG-edges incident to ix as single edges and let 1iiiGGx. Suppose that deg iiGxn. Then, the set  V,insiiXy GxyEG has at least n1s The minimum d vertices.egree of iGX is 423.23i iGX sshX inXLet yVH, HAy and aA. Another result from  (Lemma 3.1) states that there is a constant , such that, all but at most vertices ofCC iGX can red by eddisjointbe covege pies of co Hy each of them having vertex disjoint sets A. Therefore, all but at most C edges between ix and iX can be decom- posed into copies of H. All other edges inc iident tox are removed as single edges. Let 1iG consist of the remaining edges of iiGx (that is, those edges that do not belong to an H-subgraph of the above ix- decomposition). This finishes the description of the case deg iiGxn. Consider the sets 1,,nnsSxx, 1degiiGSxSx ni , and 21SSS. Let their sizes be s, 1s, and 2s respectively, so 12sss. Le tF be the gret VGapes coh witmh vertiex s thm2nsng fromoved S, consisting of the edge reH- subgraph wecessed the vertices in. Whave when pro 2Se s12 .2HHnseFsGG snsCm  () We2.9 know that  1mHns nGs HpnsGGe, rtheore, furmGn1nss . Thus, HnsGp can grabe estimGated using Lemma 2.7. If (2.6) holds, some calculations show that there exits a such that HHGG. , which contra- ph dicts the optimality go Therefore, (2.5) must hold. It follows that GGHp and thus G, depends only on Hthe degree sequence 1,,dd of G. Namely, the packing ber n numHpG equals 12m1niir, where iirddd Thereis the largest multiple of d not exceeding id. ore, f 11iio by 112idGd md1,2Hdnni mcan attain. To He an (2e need t estim valthat the degrees of do that w upper bouestimati .10)ues maxwhere ,,ndd is the degree sequence of G. 1To conclude thproof we G nd onate thee need to ng provG, the ma ximum of1=111,, =1,22nniniiiddd dmdmd (2.11) over all (not necessarily gra) sequences ,d of integers with 0=1iphical11,nddnopti. malLet sequence att1 ma,,nddx be an aining the value. For 1, ,in let iidqdr iwith 01ird. Then, 1nqqd2m. Copyright © 2012 SciRes. OJDM T. SOUSA 128 Let r with 01rd and nqd qnd. Define qd e maxi 1Rst 1n an to be integer which is at mo codulo Let thmumongruent to dd is m1d. 1and 3.0.CO;2-E  T. Gustavsson, “Decompositions of Large Graphs and Digraphs with High Minimum Degree,” Ph.D. Thesis, University of Stockholm, Stockholm, 1991.