Greedy Friensdhip Decompositions of Graphs
Teresa Sousa
DOI: 10.4236/ojdm.2011.11004   PDF    HTML     6,144 Downloads   12,831 Views  


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.

Share and Cite:

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.

Conflicts of Interest

The authors declare no conflicts of interest.


[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

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