OJAppS  Vol.2 No.4 B , December 2012
Friendship Decompositions of Graphs: The general problem
Author(s) Teresa Sousa*
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.

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.
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

 
 
Top