Friendship Decompositions of Graphs: The general problem


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.

Share and Cite:

Sousa, T. (2012) Friendship Decompositions of Graphs: The general problem. Open Journal of Applied Sciences, 2, 30-33. doi: 10.4236/ojapps.2012.24B008.

Conflicts of Interest

The authors declare no conflicts of interest.


[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

Copyright © 2024 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.