Spanning trees with at most 3 leaves in K-1,K-4-free graphs

作者：Kyaw Aung^*

来源：Discrete Mathematics, 2009, 309(20): 6146-6148.

DOI：10.1016/j.disc.2009.04.023

• Spanning tree
• Leaf
• Degree sum
• K-1,K-4-free

We present a solution of the following problem posed by Flandrin, Kaiser, Kuzel, Li and Ryjacek [E. Flandrin, T. Kaiser, R. Kuzel, H. Li and Z. Ryjacek, Discrete Math. 308(2008), 2343-2350].
Does every connected K-1,K-4-free graph G with sigma(4)(G) |G| contain a spanning tree with at most 3 leaves?
Here sigma(4)(G) = min{Sigma(4)(i=1) deg(G)(nu(i)) .{nu(1), nu(2), nu(3), nu(4)} is an independent set of G} and K-1,K-4-free graph is a graph without an induced K-1,K-4 subgraph.

• 出版日期2009-10-28