Research ArticleOpen AccessGoogle Scholar indexed
Greedy Friensdhip Decompositions of Graphs
- 1
Open Journal of Discrete Mathematics·Volume 01 (2011)·Pages 32–34·Published 8 April 2011·DOI10.4236/ojdm.2011.11004
Copy link · social · email
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.
KeywordsFriendship GraphDecompositionsGreedy Decompositions
- 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
- R. Diestel. Graph Theory. Springer-Verlag, 2nd edition, 2000.
- 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
- S. McGuinness. The greedy clique decomposition of a graph. J. Graph Theory, 18: 427-430, 1994. doi:10.1002/jgt.3190180412
- T. Sousa. Friendship decompositions of graphs. Discrete Math., 308(15): 3352-3360, 2008. doi:10.1016/j.disc.2007.06.042