Friendship Decompositions of Graphs: The general problem

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.

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.

Cite this paper

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

nullSousa, T. (2012) Friendship Decompositions of Graphs: The general problem.

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

[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