{
  "id": "1702.06203",
  "version": "v1",
  "published": "2017-02-20T23:06:34.000Z",
  "updated": "2017-02-20T23:06:34.000Z",
  "title": "Spanning Trees and Spanning Eulerian Subgraphs with Small Degrees. II",
  "authors": [
    "Morteza Hasanvand"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $G$ be a connected graph with $X\\subseteq V(G)$ and with the spanning forest $F$. Let $\\lambda\\in [0,1]$ be a real number and let $\\eta:X\\rightarrow (\\lambda,\\infty)$ be a real function. In this paper, we show that if for all $S\\subseteq X$, $\\omega(G\\setminus S)< 1+\\sum_{v\\in S}\\big(\\eta(v)-2\\big)+2\\,-\\lambda(|E_S(G)|+1)$, then $G$ has a spanning tree $T$ containing $F$ such that for each vertex $v\\in X$, $d_T(v)\\le \\lceil\\eta(v)-\\lambda\\rceil+\\max\\{0,d_F(v)-1\\}$, where $\\omega(G\\setminus S)$ denotes the number of components of $G\\setminus S$ and $E_S(G)$ denotes the set of edges of $G$ whose ends lie in the set $S$. This is an improvement of several results and the condition is best possible. Next, we show that every bipartite graph $G$ with $k$ edge-disjoint spanning trees and with the bipartition $(A,B)$ has a spanning tree $T$ such that for each vertex $v\\in A$, $d_T(v)\\le \\lceil \\frac{d_G(v)}{k}\\rceil$. This reduces the required edge-connectivity of a result due to Bar\\'at and Gerbner (2014) toward decomposing a graph into isomorphic copies of a fixed tree. Finally, we show that every $4k$-edge-connected graph with the upper bound of $4k+6$ on its degrees has a spanning Eulerian subgraph with the upper bound of $6$ on its degrees.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-02-20T23:06:34.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "spanning eulerian subgraph",
      "small degrees",
      "upper bound",
      "bipartite graph",
      "isomorphic copies"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}