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.
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.
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
|