Share This Article:

Greedy Friensdhip Decompositions of Graphs

Abstract Full-Text HTML Download Download as PDF (Size:70KB) PP. 32-34
DOI: 10.4236/ojdm.2011.11004    5,697 Downloads   12,105 Views  
Author(s)    Leave a comment


A graph that consists of t cliques sharing a vertex v is said to be a t-friendship graph with center v. A friendship graph is a graph that is t-friendship for some . We solve the problem of finding the best upper bound for the size of a greedy 2-friendship decomposition and a greedy friendship decomposition of graphs of order n.

Conflicts of Interest

The authors declare no conflicts of interest.

Cite this paper

T. Sousa, "Greedy Friensdhip Decompositions of Graphs," Open Journal of Discrete Mathematics, Vol. 1 No. 1, 2011, pp. 32-34. doi: 10.4236/ojdm.2011.11004.


[1] J. Bang-Jensen and B. Toft. Unsolved problems presented at the Julius Petersen Graph Theory Conference. Discrete Math., 101(1-3): 351-360, 1992. doi:10.1016/0012-365X(92)90616-N
[2] R. Diestel. Graph Theory. Springer-Verlag, 2nd edition, 2000.
[3] P. Erd?s, A. W. Goodman, and L. Pósa, The representation of a graph by set intersections, Canad. J. Math. 18: 106-112, 1966. doi:10.4153/CJM-1966-014-3
[4] S. McGuinness. The greedy clique decomposition of a graph. J. Graph Theory, 18: 427-430, 1994. doi:10.1002/jgt.3190180412
[5] T. Sousa. Friendship decompositions of graphs. Discrete Math., 308(15): 3352-3360, 2008. doi:10.1016/j.disc.2007.06.042

comments powered by Disqus

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