Paper Menu >>
Journal Menu >>
Friendship Decompositions of Graphs:The general problem Teresa Sousa∗ Departamento de Matem´atica and Centro de Matem´atica e Aplica¸c˜oes Faculdade de Ciˆencias e Tecnologia, Universidade Novade Lisboa Quinta da Torre, 2829-516 Caparica, Portugal tmjs@fct.unl.pt September 24, 2012 Abstract– A friendshipgraph isa graphconsisting ofcliques sharinga commonvertex.In thispaper we investigate the maximum number of elements in an optimal friendship decomposition of graphs of order n.We obtain upper and lower bounds for this number.These bounds relate this problem with the classical Ramsey numbers. Keywords: Graph Decompositions; Friendship Graph; Friendship Decompositions 1 Introduction For notation and terminology the reader is referred to [1].All graphsconsideredhereare finiteand simple, i.e., they have no loops or multiple edges. Let Hbe a fixed family of graphs.An H- decomposition of a given graph Gis a partition of its edge set into subgraphs that are isomorphic to elements of H.We define φ(G, H) as the mini- mum number of elements in an H-decomposition of G.One ofthe main problemsin graphdecom- positionsis the one of findingthe smallest number φ(n, H), such that, anygraph oforder nadmits an H-decomposition with at most φ(n, H)elements. This problem has been studied for some well known families ofgraphs, such as, cliques, bipartitegraphs, cycles and paths. Aclique is a complete graph and a clique de- composition or a cliquepartitionof agraph isa decomposition of itsedge set intoedge disjoint cliques. Erd˝os, Goodman and P´osa [2] showed that the edgesof anygraph onnvertices canbe de- composed into at most n2/4cliques.They also showed that aminimum cliquedecompositionhas exactly n2/4cliquesif andonly ifthe graphis pre- cisely Kn/2,n/2.Further,inthe decomposition they onlyneedto useedgesandtriangles.Later Bollob´as [3]generalized this resultby showingthat a graph of order ncan be decomposed into at most tp−1(n) edge disjoint cliquesof orderp(p≥4) and single edges.By tp−1(n)wedenotethenumberof edges inthe Tur´angraph of ordern,Tp−1(n), which is the uniquecomplete (p−1)-partite graphon n vertices that has themaximum number ofedges. Furthermore,for p≥4it wasalsoproved that Tp−1(n)istheonlygraph thatcannotbedecom- posed into fewer than tp−1(n) edge disjoint cliques of order pand single edges. Let Bdenote thefamilyof allcomplete bipar- tite graphs.It is easyto see thatthe edgesof thecompletegraphKncanbe decomposed into n−1 edgedisjointcomplete bipartite subgraphs, since Kndecomposesinto edge disjointcopiesof the starsK1,n−1,K 1,n−2,...,K 1,2,K 1,1. Graham and Pollak[4] proved that Kncannot be partitioned into 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 and simple proofs were found later by Tverberg [5] and Peck [6]. Consider now the family Cof all cycles, then it is easyto seethat agraphadmits acycle decompo- sition ifan onlyif allits verticeshaveevendegree. In this case, Haj´os made the following conjecture. Conjecture 1.Every graphGon nverticeswith all degrees even can bedecomposed into at most n/2edge disjointcycles. Open Journal of Applied Sciences Supplement:2012 world Congress on Engineering and Technology 30 Cop y ri g ht © 2012 SciRes. In this direction Lov´asz [7] proved thefollowing theorem: Theorem 1.1. A graph on nvertices can be de- composed into at most n/2edge disjoint paths and cycles. This theorem includes the following two results concerning complete graphs:the completegraph on 2kverticescan be decomposedinto kedge disjoint paths and thecomplete graph on 2k+1 vertices can bedecomposedinto kedge disjointHamiltonian cy- cles. Lov´asz theorem is also a partial result towards the following conjecture of Gallai. Conjecture 2.Agraphororder ncan bedecom- posedinto at most (n+1)/2paths. Let Pbethefamily ofallpaths.Deanand Kouider[8] showedthatfor anygraphG(possi- bly disconnected), φ(G, P)≤u(G)/2+2 3g(G), where u(G) denotes the number of odd verticesin Gandg(G) denotesthe number of nonisolatedeven vertices in G. In this paper we will studydecompositions of graphs into friendship graphs.Afriendship graph is agraph consistingof cliquessharing acommon vertex.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 [9]determinedthe exact value ofthefunctionφ(n, Ft)fort=2 andt=3, and its asymptoticvaluefor t≥4.More precisely, Sousa [9] proved the following theorems. Theorem 1.2 (Sousa[9]).Let F2bethe set of all 2-friendship graphs.We have, φ(n, F2)=⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ n2 8if nis even, n2−1 8if nis odd. Theorem 1.3 (Sousa[9]).Let F3bethe set of all 3-friendship graphs.We have, φ(n, F3)= ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ n2 12 if nis even, n2−1 12 if nis odd and n=5, 3if n=5. Theorem 1.4(Sousa [9]).Let t≥4andlet Ftbe the setof all t-friendship graphs.We have, φ(n, Ft)=1 4t+o(1)n2. Let Fbe the set of all friendship graphs.Our goal is to study the functionφ(n, F), which is the smallest number suchthat any graphof order n admits afriendshipdecomposition withatmost φ(n, F) elements.The exactvalue ofthe func- tion φ(n, F) isstill unknown.However, for nsuffi- ciently large,wewereable toobtain lower andup- per bounds (see Theorem 1.5below).These results relate the functionφ(n, F) with the classical Ram- sey numbers, which might be an indication that the problem offindingtheexact value of thefunction φ(n, F) might be deep and hard. Theorem 1.5.Let Fbe the set of all friendship graphs.There exists n0suchthat for alln≥n0we have n−9nlog n≤φ(n,F)≤n−1 2log2 n 4. 2Friendship Decompositions in this section we willproveTheorem 1.5.Westart with some definitions and auxiliary results. Definition 2.1.Let Gbea graph. (a)Avertex cover of Gisa set S⊂V(G)such that every edge ofGis incidentwith a vertex of S.The minimum size of a vertex cover of Gis denoted byα0(G). (b)AsubsetA⊂V(G)issaidtobeindependent if no two vertices of Aare adjacent in G.The independence numberof a graphGis the max- imum size of an independent set of vertices and is denotedby α(G). Observation 2.2.Ina graphG,S⊂V(G)isa vertex 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). Cop y ri g ht © 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,...,v m},wherem=α0(G). Let S={Svi|i=1,...,m}where Svidenotes the star with center viand edge set E(Svi)={vi,x}|{vi,x}∈E(G)−∪ i−1 j=1E(Svj). Clearly Sis afriendship decomposition of G,hence φ(G, F)≤|S|=α0(G). (b) Itsuffices tosee thatα0(G)≤φ(G, F). In thiscase allfriendshipsubgraphsofGarestars. Thus, ifSisafriendshipdecomposition ofGwith |S| =φ(G, F) then the set of vertices {v| vis the center of F, F ∈S}isa vertexcoverfor G.Therefore α0(G)≤|S|=φ(G, F). We will alsoneed some results from Ramsey The- ory.We start with the definition of the Ramsey numbers. Definition 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 on nor morevertices, thereexists either aclique ofs vertices or an independent set of tvertices. The existenceof these Ramseynumbers is a simple consequence of a theorem proved by Ram- sey [10].The problem of estimating R(s, t)oreven R(s, s) hasproved tobevery difficultand thebest known bounds are still quite far apart.Erd˝os and Szekeres [11]showed that R(s, t)≤s+t−2 s−1which implies that R(s, s)≤2s−2 s−1≤22s−2(2.1) The best known upper bound on R(s, s)was proved by Thomason in [12] where he shows that R(s, s)≤s(−1 2+o(1))2s−2 s−1.In one of the first applications of the probabilistic method Erd˝os [?] proved an exponential lower bound on R(s, s)us- ing random colorings.These boundswereimproved later by Spencer in [13] where he uses the proba- bilistic method andLov´asz Local Lemmatoobtain R(s, s)>√2 e1+o(1)s2s/2and this is the best known lowerboundforR(s, s). The gap betweenthese bounds is still large, and in recentyears, relatively littleprogress has been made.Tight bounds are known only for s=3. We have, c1 t2 log t≤R(3,t)≤c2 t2 log t. The upper bound is due to Ajtai, Koml´os and Sze- mer´edi [14]andthe lowerbound wasproved by Kim [15]using a probabilistic argument.The main result ofKim, which willbeused in theproofof Theorem 1.5, is the following upper bound on the independence number of triangle free graphs. Theorem2.5. Let G(3) ndenote a triangle free graphon nvertices.Thenevery sufficientlylarge nhas a G(3) nfor which α(G(3) n)≤9nlog n, wherelog denotes the natural logarithm. We are now able to prove Theorem 1.5 Proof of Theorem 1.5.Letnbesufficiently large and let G(3) nbe asin Theorem 2.5.From Lemma 2.3 we know that φ(G(3) n,F)=α0(G(3) n) and from Observation 2.2 we have α0(G(3) n)=n−α(G(3) n). Therefore, φ(G(3) n,F)≥n−9nlogn by Theorem 2.5 and this implies the lower bound. It remains to prove the upper bound.Let Gbea graph oforder nand lett=1 2log2n+1. Then, by (2.1) we have R(t,t)≤nand this impliesthat Gcontains either an independent set oftvertices or acliqueof tvertices. (a)Suppose that Gcontains an independent set of tvertices, sayTand letX:= V(G)−T. Assume that theelementsof Xare orderedand let X={v1,...,v m},wherem=n−t.Let S={Svi|i=1,...,m},whereSvidenotes the star with center viand edge set E(Svi)={vi,x}|{vi,x}∈E(G)−∪i−1 j=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 the graph obtainedfrom Gafter the deletion of the edges ofG[X].NowG1containsan indepen- dent set of tvertices, so φ(G1,F)≤n−tby part (a), therefore φ(G, F)≤n−t+1. We have n−t+1≤n−1 2log2n−1+2= n−1 2log2 n 4, as required. 32 Cop y ri g ht © 2012 SciRes. 3 Acknowledgments T. S. thanks Oleg Pikhurko for helpful comments and discussions,and the support from FCT - Funda¸c˜ao para a Ciˆencia e a Tecnologia (Portugal), through Projects PTDC/MAT/113207/2009 and PEst-OE/MAT/UI0297/2011 (CMA), financed by the European Community Fund FEDER through the COMPETE-CompetitivenessFactors Opera- tional Programme. References [1] B.Bollob´as,“ModernGraphTheory,” Springer-Verlag, New York, 1998, xiii+394pp. [2]P. Erd˝os, A. W. Goodmanand L.P´osa,“The representation of a graph by set intersections,” Can. J. Math., Vol. 18, 1966, pp. 106-112. [3]B. Bollob´as, “On complete subgraphs of differ- ent orders,” Math. Proc. Camb. Phil. Soc., Vol 79, 1976, pp. 19-24. [4]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. [5]H. Tverberg. “On the decomposition of Kn into completebipartitegraphs.”,J. Graph Theory, Vol. 6, 1982, pp. 493-494. [6] G. W. Peck, “A new proof of a theoremof Graham andPollak,” DiscreteMath., Vol. 49, 1984, pp. 327-328. [7]L. Lov´asz, “On coveringofgraphs,” In “The- ory ofGraphs (Proc. Colloq., Tihany, 1966)”, Academic Press, 1968, pp. 231-236. [8]N.Dean and M.Kouider, “Gallai’sconjecture for disconnectedgraphs,” Discrete Math.,Vol. 213, 2000, pp. 43-54. [9] T.Sousa,“FriendshipDecompositionof graphs,”DiscreteMath., Vol.308, 2008, pp. 3352-3360. [10]F. P. Ramsey,“On a Problem of Formal Logic,” Proc. London Math.Soc.,Vol. 30, 1930, pp. 264-286. [11] P. Erd˝os and G. Szekeres,“A combinatorial problem ingeometry,” Compositio Math., Vol. 2, 1935, pp. 463-470. [12]A. Thomason,“An upper bound for some Ramseynumbers,” J.GraphTheory, Vol. 12, 1988, pp. 509-517. [13]J. Spencer,“Asymptotic lower bounds for Ramsey functions,” Discrete Math.,Vol. 20, 1977/78, pp. 69-76. [14] M. Ajtai, J.Koml´os andE. Szemer´edi,“A note on Ramsey numbers,” J. Combin. Theory Ser. A, Vol. 29, 1980, pp. 354-360. [15]J. H. Kim, “The Ramsey number R(3,t)has order of magnitude t2/logt,” Random Struc- tures Algorithms, Vol. 7, 1995, pp. 173-207. Cop y ri g ht © 2012 SciRes.33 |