科研之友
微信
新浪微博
Facebook
分享链接
摘要
Solving a problem raised by BONDY and SZWARCFITER [J. Graph Theory, 72 (2013), 462-477], we prove that if the edge set of a graph G of order n can be decomposed into edge-disjoint induced copies of the path P-4 or of the paw K-4 - P-3 then the complement of G has at least cn(3/2) edges. This lower bound is tight apart from the actual value of c, and settles the previously unsolved cases for the graphs with at most four vertices. More generally the lower bound cn(3/2) holds for any graph without isolated vertices which is not a complete multipartite graph; but a linear upper bound is valid for any complete tripartite graph.
- 出版日期2014-10
