Friendship Decompositions of Graphs: The general problem

Teresa Sousa

Departamento de Matematica and Centro de Matematica e Aplicac~oes Faculdade de Ci^encias e Tecnologia, Universidade Nova de Lisboa Quinta da Torre, 2829-516 Caparica, Portugal.

DOI: 10.4236/ojapps.2012.24B008                

Abstract

A friendship graph is a graph consisting of cliques sharing a common vertex. In this paper 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

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	B. Bollobas, “Modern Graph Theory,” Springer-Verlag, New York, 1998, xiii+394pp.
[2]	P. Erdos, A. W. Goodman and L. Posa, “The representation of a graph by set intersections,” Can. J. Math., Vol. 18, 1966, pp. 106-112.
[3]	B. Bollobas, “On complete subgraphs of different orders," Math. Proc. Camb. Phil. Soc., Vol. 79, 1976, pp. 19-24.
[4]	R. L. Graham and H. O. Pollak, “On the addressing problem for loop switching,” Bell System Tech. J., Vol. 50, 1971, pp. 2495-259.
[5]	H. Tverberg. “On the decomposition of Kn into complete bipartite graphs.” , J. Graph Theory, Vol. 6, 1982, pp. 493-494.
[6]	G. W. Peck, “A new proof of a theorem of Graham and Pollak,” Discrete Math., Vol. 49, 1984, pp. 327-328.
[7]	L. Lovasz, “On covering of graphs,” In “Theory of Graphs (Proc. Colloq., Tihany, 1966)”, Academic Press, 1968, pp. 231-236.
[8]	N. Dean and M. Kouider, “Gallai's conjecture for disconnected graphs,” Discrete Math., Vol. 213, 2000, pp. 43-54.
[9]	T. Sousa, “Friendship Decomposition of graphs,” Discrete Math., 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. Erdos and G. Szekeres, “A combinatorial problem in geometry,” Compositio Math., Vol. 2, 1935, pp. 463-470.
[12]	A. Thomason, “An upper bound for some Ramsey numbers,” J. Graph Theory, 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. Komlos and E. Szemeredi, “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/log t,” Random Structures Algorithms, Vol. 7, 1995, pp. 173-207