Share This Article:

Friendship Decompositions of Graphs: The general problem

Abstract Full-Text HTML Download Download as PDF (Size:132KB) PP. 30-33
DOI: 10.4236/ojapps.2012.24B008    2,060 Downloads   3,334 Views  
Author(s)    Leave a comment

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.

Conflicts of Interest

The authors declare no conflicts of interest.

Cite this paper

Sousa, 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

  
comments powered by Disqus

Copyright © 2018 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.