A spanning tree with no more than 3 leaves is called a spanning 3-ended tree. In this paper, we prove that if G is a k-connected （k≥ 2） almost claw-free graph of order n and σk＋3（G） ≥ n ＋ k ＋ 2, then G conta...A spanning tree with no more than 3 leaves is called a spanning 3-ended tree. In this paper, we prove that if G is a k-connected （k≥ 2） almost claw-free graph of order n and σk＋3（G） ≥ n ＋ k ＋ 2, then G contains a spanning 3-ended tree, where σk（G） = min{∑es deg（v） ： S is an independent set of G with ｜S｜ = k}.展开更多
A graph is called claw-free if it contains no induced subgrapn lsomorpmc to K1,3. Matthews and Sumner proved that a 2-connected claw-free graph G is Hamiltonian if every vertex of it has degree at least （[V（G）I - 2...A graph is called claw-free if it contains no induced subgrapn lsomorpmc to K1,3. Matthews and Sumner proved that a 2-connected claw-free graph G is Hamiltonian if every vertex of it has degree at least （[V（G）I - 2）/3. At the workshop CSzC （Novy Smokovec, 1993）, Broersma conjectured the degree condition of this result can be restricted only to end-vertices of induced copies of N （the graph obtained from a triangle by adding three disjoint pendant edges）. Fujisawa and Yamashita showed that the degree condition of Matthews and Sumner can be restricted only to end-vertices of induced copies of Z1 （the graph obtained from a triangle by adding one pendant edge）. Our main result in this paper is a characterization of all graphs H such that a 2-connected claw-free graph G is Hamiltonian if eachend-vertex of every induced copy of H in G has degree at least IV（G）I/3 ＋ 1. This gives an affirmative solution of the conjecture of Broersma up to an additive constant.end-vertex of every induced copy of H in G has degree at least IV（G）I/3 ＋ 1. This gives an affirmative solution of the conjecture of Broersma up to an additive constant.展开更多
基金Supported by the National Natural Science Foundation of China,Tian Yuan Special Foundation(Grant No.11426125)by Educational Commission of Liaoning Province(Grant No.L2014239)
文摘A spanning tree with no more than 3 leaves is called a spanning 3-ended tree. In this paper, we prove that if G is a k-connected （k≥ 2） almost claw-free graph of order n and σk＋3（G） ≥ n ＋ k ＋ 2, then G contains a spanning 3-ended tree, where σk（G） = min{∑es deg（v） ： S is an independent set of G with ｜S｜ = k}.
基金Supported by NSFC(Grant Nos.11271300 and 11571135)the project NEXLIZ–CZ.1.07/2.3.00/30.0038+1 种基金the project P202/12/G061 of the Czech Science Foundation and by the European Regional Development Fund(ERDF)the project NTIS-New Technologies for Information Society,European Centre of Excellence,CZ.1.05/1.1.00/02.0090
文摘A graph is called claw-free if it contains no induced subgrapn lsomorpmc to K1,3. Matthews and Sumner proved that a 2-connected claw-free graph G is Hamiltonian if every vertex of it has degree at least （[V（G）I - 2）/3. At the workshop CSzC （Novy Smokovec, 1993）, Broersma conjectured the degree condition of this result can be restricted only to end-vertices of induced copies of N （the graph obtained from a triangle by adding three disjoint pendant edges）. Fujisawa and Yamashita showed that the degree condition of Matthews and Sumner can be restricted only to end-vertices of induced copies of Z1 （the graph obtained from a triangle by adding one pendant edge）. Our main result in this paper is a characterization of all graphs H such that a 2-connected claw-free graph G is Hamiltonian if eachend-vertex of every induced copy of H in G has degree at least IV（G）I/3 ＋ 1. This gives an affirmative solution of the conjecture of Broersma up to an additive constant.end-vertex of every induced copy of H in G has degree at least IV（G）I/3 ＋ 1. This gives an affirmative solution of the conjecture of Broersma up to an additive constant.
