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
tp1(n) edge disjoint cliquesof orderp(p4) and
single edges.By tp1(n)wedenotethenumberof
edges inthe Tur´angraph of ordern,Tp1(n), which
is the uniquecomplete (p1)-partite graphon n
vertices that has themaximum number ofedges.
Furthermore,for p4it wasalsoproved that
Tp1(n)istheonlygraph thatcannotbedecom-
posed into fewer than tp1(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
n1 edgedisjointcomplete bipartite subgraphs,
since Kndecomposesinto edge disjointcopiesof
the starsK1,n1,K
1,n2,...,K
1,2,K
1,1. Graham
and Pollak[4] proved that Kncannot be partitioned
into fewer than n1 edge disjoint completebipar-
tite graphs.Therefore, φ(Kn,B)=n1.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
Supplement2012 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 t2, 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 t4.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,
n21
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,
n21
12 if nis odd and n=5,
3if n=5.
Theorem 1.4(Sousa [9]).Let t4andlet 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 allnn0we
have
n9nlog nφ(n,F)n1
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 SV(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)AsubsetAV(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,SV(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)−∪
i1
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+t2
s1which
implies that
R(s, s)2s2
s122s2(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))2s2
s1.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 tR(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)n9nlogn
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=nt.Let
S={Svi|i=1,...,m},whereSvidenotes the
star with center viand edge set
E(Svi)={vi,x}|{vi,x}∈E(G)−∪i1
j=1E(Svj).
Clearly Sis a friendship decomposition of G,
hence φ(G, F)≤|S|=|X|=nt.
(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)ntby
part (a), therefore φ(G, F)nt+1.
We have nt+1n1
2log2n1+2= n1
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