没有5-圈的平面图的BB-染色

设H为G的一个生成子图,（G,H）的一个BB-k-染色是指一个映射f：V（G）→{1,2,…,k},当uv∈E（H）,｜f（u）-f（v）｜≥2;当uv∈E（G）／E（H）,｜f（u）-f（v）｜≥1.定义（G,H）的BB色数x_b（G,H）为最小的整数k,使得（G,H）是BB-k可染的.本文研究了对于任意的连通,非二部平面图G,且G没有5-圈,都存在一棵生成树T,使得x_b（G,T）=4.     

Extended formulations for matroid polytopes through randomized protocols

The hitting number of a polytope P is the smallest size of a subset of vertices of P such that every facet of P has a vertex in the subset. We show that, if P is the base polytope of any matroid, then P admits an extended formulation of linear size on the hitting number of P. Our results generalize those of the spanning tree polytope given by Martin and Wong, and extend to polymatroids.     

Minimum-weight two-connected spanning networks

We consider the problem of constructing a minimum-weight, two-connected network spanning all the points in a setV. We assume a symmetric, nonnegative distance functiond(·) defined onV × V which satisfies the triangle inequality. We obtain a structural characterization of optimal solutions. Specifically, there exists an optimal two-connected solution whose vertices all have degree 2 or 3, and such that the removal of any edge or pair of edges leaves a bridge in the resulting connected components. These are the strongest possible conditions on the structure of an optimal solution since we also show thatany two-connected graph satisfying these conditions is theunique optimal solution for a particular choice of canonical distances satisfying the triangle inequality. We use these properties to show that the weight of an optimal traveling salesman cycle is at most 4/3 times the weight of an optimal two-connected solution; examples are provided which approach this bound arbitrarily closely. In addition, we obtain similar results for the variation of this problem where the network need only span a prespecified subset of the points.     

Spanning trees with at most 4 leaves in K1,5-free graphs

In 2009, Kyaw proved that every $n$-vertex connected $K_{1,4}$-free graph $G$ with ${\sigma }_4\left(G\right)\ge n?1$ contains a spanning tree with at most 3 leaves. In this paper, we prove an analogue of Kyaw’s result for connected $K_{1,5}$-free graphs. We show that every $n$-vertex connected $K_{1,5}$-free graph $G$ with ${\sigma }_5\left(G\right)\ge n?1$ contains a spanning tree with at most 4 leaves. Moreover, the degree sum condition “${\sigma }_5\left(G\right)\ge n?1$” is best possible.