Back
 OJDM  Vol.1 No.1 , April 2011
Greedy Friensdhip Decompositions of Graphs
Abstract: 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.
Cite this paper: nullT. 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.
References

[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

 
 
Top