 Friendship Decompositions of Graphs:The general problemTeresa Sousa∗Departamento de Matem´atica and Centro de Matem´atica e Aplica¸c˜oesFaculdade de Ciˆencias e Tecnologia, Universidade Novade LisboaQuinta da Torre, 2829-516 Caparica, Portugaltmjs@fct.unl.ptSeptember 24, 2012Abstract– A friendshipgraph isa graphconsisting ofcliques sharinga commonvertex.In thispaperwe investigate the maximum number of elements in an optimal friendship decomposition of graphs oforder n.We obtain upper and lower bounds for this number.These bounds relate this problem with theclassical Ramsey numbers.Keywords: Graph Decompositions; Friendship Graph; Friendship Decompositions1 IntroductionFor notation and terminology the reader is referredto .All graphsconsideredhereare ﬁniteandsimple, i.e., they have no loops or multiple edges.Let Hbe a ﬁxed family of graphs.An H-decomposition of a given graph Gis a partition ofits edge set into subgraphs that are isomorphic toelements of H.We deﬁne φ(G, H) as the mini-mum number of elements in an H-decompositionof G.One ofthe main problemsin graphdecom-positionsis the one of ﬁndingthe smallest numberφ(n, H), such that, anygraph oforder nadmitsan H-decomposition with at most φ(n, H)elements.This problem has been studied for some well knownfamilies ofgraphs, such as, cliques, bipartitegraphs,cycles and paths.Aclique is a complete graph and a clique de-composition or a cliquepartitionof agraph isadecomposition of itsedge set intoedge disjointcliques. Erd˝os, Goodman and P´osa  showed thatthe edgesof anygraph onnvertices canbe de-composed into at most n2/4cliques.They alsoshowed that aminimum cliquedecompositionhasexactly n2/4cliquesif andonly ifthe graphis pre-cisely Kn/2,n/2.Further,inthe decompositionthey onlyneedto useedgesandtriangles.LaterBollob´as generalized this resultby showingthata graph of order ncan be decomposed into at mosttp−1(n) edge disjoint cliquesof orderp(p≥4) andsingle edges.By tp−1(n)wedenotethenumberofedges inthe Tur´angraph of ordern,Tp−1(n), whichis the uniquecomplete (p−1)-partite graphon nvertices that has themaximum number ofedges.Furthermore,for p≥4it wasalsoproved thatTp−1(n)istheonlygraph thatcannotbedecom-posed into fewer than tp−1(n) edge disjoint cliquesof order pand single edges.Let Bdenote thefamilyof allcomplete bipar-tite graphs.It is easyto see thatthe edgesofthecompletegraphKncanbe decomposed inton−1 edgedisjointcomplete bipartite subgraphs,since Kndecomposesinto edge disjointcopiesofthe starsK1,n−1,K1,n−2,...,K1,2,K1,1. Grahamand Pollak proved that Kncannot be partitionedinto fewer than n−1 edge disjoint completebipar-tite graphs.Therefore, φ(Kn,B)=n−1.This re-sult of Graham and Pollak was motivated by an ad-dressing problemin communications networks andsimple proofs were found later by Tverberg  andPeck .Consider now the family Cof all cycles, then itis easyto seethat agraphadmits acycle decompo-sition ifan onlyif allits verticeshaveevendegree.In this case, Haj´os made the following conjecture.Conjecture 1.Every graphGon nverticeswithall degrees even can bedecomposed into at mostn/2edge disjointcycles.Open Journal of Applied Sciences Supplement：2012 world Congress on Engineering and Technology30 Copyright © 2012 SciRes. In this direction Lov´asz  proved thefollowingtheorem:Theorem 1.1. A graph on nvertices can be de-composed into at most n/2edge disjoint paths andcycles.This theorem includes the following two resultsconcerning complete graphs:the completegraph on2kverticescan be decomposedinto kedge disjointpaths and thecomplete graph on 2k+1 vertices canbedecomposedinto kedge disjointHamiltonian cy-cles. Lov´asz theorem is also a partial result towardsthe following conjecture of Gallai.Conjecture 2.Agraphororder ncan bedecom-posedinto at most (n+1)/2paths.Let Pbethefamily ofallpaths.DeanandKouider showedthatfor anygraphG(possi-bly disconnected), φ(G, P)≤u(G)/2+23g(G),where u(G) denotes the number of odd verticesinGandg(G) denotesthe number of nonisolatedevenvertices in G.In this paper we will studydecompositions ofgraphs into friendship graphs.Afriendship graphis agraph consistingof cliquessharing acommonvertex.For t≥2, a t-friendship graph isafriend-ship graph that consists of exactly tcliques shar-ing a common vertex.Let Ftbe the set of all t-friendship graphs.Sousa determinedthe exactvalue ofthefunctionφ(n, Ft)fort=2 andt=3,and its asymptoticvaluefor t≥4.More precisely,Sousa  proved the following theorems.Theorem 1.2 (Sousa).Let F2bethe set of all2-friendship graphs.We have,φ(n, F2)=⎧⎪⎪⎪⎨⎪⎪⎪⎩n28if nis even,n2−18if nis odd.Theorem 1.3 (Sousa).Let F3bethe set of all3-friendship graphs.We have,φ(n, F3)=⎧⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎩n212 if nis even,n2−112 if nis odd and n=5,3if n=5.Theorem 1.4(Sousa ).Let t≥4andlet Ftbethe setof all t-friendship graphs.We have,φ(n, Ft)=14t+o(1)n2.Let Fbe the set of all friendship graphs.Ourgoal is to study the functionφ(n, F), which is thesmallest number suchthat any graphof order nadmits afriendshipdecomposition withatmostφ(n, F) elements.The exactvalue ofthe func-tion φ(n, F) isstill unknown.However, for nsuﬃ-ciently large,wewereable toobtain lower andup-per bounds (see Theorem 1.5below).These resultsrelate the functionφ(n, F) with the classical Ram-sey numbers, which might be an indication that theproblem ofﬁndingtheexact value of thefunctionφ(n, F) might be deep and hard.Theorem 1.5.Let Fbe the set of all friendshipgraphs.There exists n0suchthat for alln≥n0wehaven−9nlog n≤φ(n,F)≤n−12log2n4.2Friendship Decompositionsin this section we willproveTheorem 1.5.Westartwith some deﬁnitions and auxiliary results.Deﬁnition 2.1.Let Gbea graph.(a)Avertex cover of Gisa set S⊂V(G)suchthat every edge ofGis incidentwith a vertexof S.The minimum size of a vertex cover ofGis denoted byα0(G).(b)AsubsetA⊂V(G)issaidtobeindependentif no two vertices of Aare adjacent in G.Theindependence numberof a graphGis the max-imum size of an independent set of vertices andis denotedby α(G).Observation 2.2.Ina graphG,S⊂V(G)isavertex cover if and only if V(G)\Sis an indepen-dent set, and henceα0(G)+α(G)=v(G).Lemma 2.3.Let Gbea graph.We have,(a) φ(G, F)≤α0(G);(b) If,inaddition,Gis triangle free thenφ(G, F)=α0(G).Copyright © 2012 SciRes.31 Proof.(a) Let Cbe a vertex cover of Gsuch that|C| =α0(G) and assume that its elements are or-dered, i.e.,C={v1,...,vm},wherem=α0(G).Let S={Svi|i=1,...,m}where Svidenotes thestar with center viand edge setE(Svi)={vi,x}|{vi,x}∈E(G)−∪i−1j=1E(Svj).Clearly Sis afriendship decomposition of G,henceφ(G, F)≤|S|=α0(G).(b) Itsuﬃces tosee thatα0(G)≤φ(G, F). Inthiscase allfriendshipsubgraphsofGarestars.Thus, ifSisafriendshipdecomposition ofGwith|S| =φ(G, F) then the set of vertices {v|vis the center of F, F ∈S}isa vertexcoverforG.Therefore α0(G)≤|S|=φ(G, F).We will alsoneed some results from Ramsey The-ory.We start with the deﬁnition of the Ramseynumbers.Deﬁnition 2.4.Let sand tbenaturalnumbers.The Ramsey number of sand t, denoted byR(s, t),is the smallest integer n, such that, in any graph onnor morevertices, thereexists either aclique ofsvertices or an independent set of tvertices.The existenceof these Ramseynumbers is asimple consequence of a theorem proved by Ram-sey .The problem of estimating R(s, t)orevenR(s, s) hasproved tobevery diﬃcultand thebestknown bounds are still quite far apart.Erd˝os andSzekeres showed that R(s, t)≤s+t−2s−1whichimplies thatR(s, s)≤2s−2s−1≤22s−2(2.1)The best known upper bound on R(s, s)wasproved by Thomason in  where he shows thatR(s, s)≤s(−12+o(1))2s−2s−1.In one of the ﬁrstapplications of the probabilistic method Erd˝os [?]proved an exponential lower bound on R(s, s)us-ing random colorings.These boundswereimprovedlater by Spencer in  where he uses the proba-bilistic method andLov´asz Local LemmatoobtainR(s, s)>√2e1+o(1)s2s/2and this is the bestknown lowerboundforR(s, s).The gap betweenthese bounds is still large, andin recentyears, relatively littleprogress has beenmade.Tight bounds are known only for s=3. Wehave,c1t2log t≤R(3,t)≤c2t2log t.The upper bound is due to Ajtai, Koml´os and Sze-mer´edi andthe lowerbound wasproved byKim using a probabilistic argument.The mainresult ofKim, which willbeused in theproofofTheorem 1.5, is the following upper bound on theindependence number of triangle free graphs.Theorem2.5. Let G(3)ndenote a triangle freegraphon nvertices.Thenevery suﬃcientlylargenhas a G(3)nfor whichα(G(3)n)≤9nlog n,wherelog denotes the natural logarithm.We are now able to prove Theorem 1.5Proof of Theorem 1.5.Letnbesuﬃciently largeand let G(3)nbe asin Theorem 2.5.From Lemma 2.3we know that φ(G(3)n,F)=α0(G(3)n) and fromObservation 2.2 we have α0(G(3)n)=n−α(G(3)n).Therefore,φ(G(3)n,F)≥n−9nlognby Theorem 2.5 and this implies the lower bound.It remains to prove the upper bound.Let Gbeagraph oforder nand lett=12log2n+1. Then,by (2.1) we have R(t,t)≤nand this impliesthatGcontains either an independent set oftverticesor acliqueof tvertices.(a)Suppose that Gcontains an independent setof tvertices, sayTand letX:= V(G)−T.Assume that theelementsof Xare orderedandlet X={v1,...,vm},wherem=n−t.LetS={Svi|i=1,...,m},whereSvidenotes thestar with center viand edge setE(Svi)={vi,x}|{vi,x}∈E(G)−∪i−1j=1E(Svj).Clearly Sis a friendship decomposition of G,hence φ(G, F)≤|S|=|X|=n−t.(b)Now suppose that Gcontains a clique of tver -tices, sayG[X], with|X|=t.LetG1be thegraph obtainedfrom Gafter the deletion of theedges ofG[X].NowG1containsan indepen-dent set of tvertices, so φ(G1,F)≤n−tbypart (a), therefore φ(G, F)≤n−t+1.We have n−t+1≤n−12log2n−1+2= n−12log2n4,as required.32 Copyright © 2012 SciRes. 3 AcknowledgmentsT. S. thanks Oleg Pikhurko for helpful commentsand discussions,and the support from FCT -Funda¸c˜ao para a Ciˆencia e a Tecnologia (Portugal),through Projects PTDC/MAT/113207/2009 andPEst-OE/MAT/UI0297/2011 (CMA), ﬁnanced bythe European Community Fund FEDER throughthe COMPETE-CompetitivenessFactors Opera-tional Programme.References B.Bollob´as,“ModernGraphTheory,”Springer-Verlag, New York, 1998, xiii+394pp.P. Erd˝os, A. W. Goodmanand L.P´osa,“Therepresentation of a graph by set intersections,”Can. J. Math., Vol. 18, 1966, pp. 106-112.B. Bollob´as, “On complete subgraphs of diﬀer-ent orders,” Math. Proc. Camb. Phil. Soc., Vol79, 1976, pp. 19-24.R. L. Grahamand H. O. Pollak, “On the ad-dressing problem for loop switching,” Bell Sys-tem Tech. J., Vol. 50, 1971, pp. 2495-259.H. Tverberg. “On the decomposition of Kninto completebipartitegraphs.”,J. GraphTheory, Vol. 6, 1982, pp. 493-494. G. W. Peck, “A new proof of a theoremofGraham andPollak,” DiscreteMath., Vol. 49,1984, pp. 327-328.L. Lov´asz, “On coveringofgraphs,” In “The-ory ofGraphs (Proc. Colloq., Tihany, 1966)”,Academic Press, 1968, pp. 231-236.N.Dean and M.Kouider, “Gallai’sconjecturefor disconnectedgraphs,” Discrete Math.,Vol.213, 2000, pp. 43-54. T.Sousa,“FriendshipDecompositionofgraphs,”DiscreteMath., Vol.308, 2008, pp.3352-3360.F. P. Ramsey,“On a Problem of FormalLogic,” Proc. London Math.Soc.,Vol. 30,1930, pp. 264-286. P. Erd˝os and G. Szekeres,“A combinatorialproblem ingeometry,” Compositio Math., Vol.2, 1935, pp. 463-470.A. Thomason,“An upper bound for someRamseynumbers,” J.GraphTheory, Vol. 12,1988, pp. 509-517.J. Spencer,“Asymptotic lower bounds forRamsey functions,” Discrete Math.,Vol. 20,1977/78, pp. 69-76. M. Ajtai, J.Koml´os andE. Szemer´edi,“Anote on Ramsey numbers,” J. Combin. TheorySer. A, Vol. 29, 1980, pp. 354-360.J. H. Kim, “The Ramsey number R(3,t)hasorder of magnitude t2/logt,” Random Struc-tures Algorithms, Vol. 7, 1995, pp. 173-207.Copyright © 2012 SciRes.33