Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Spanning trees in connected graphs with few branch and end vertices   A vertex of degree one in a tree is called an end vertex and a vertex of
degree at least three is called a branch vertex. For a graph $G$, let
$\sigma_2$ be the minimum degree sum of two nonadjacent vertices in $G$. We
consider tree problems arising in the context of optical and centralized
terminal networks: finding a spanning tree of G (i) with the minimum number of
end vertices, (ii) with the minimum number of branch vertices and (iii) with
the minimum degree sum of the branch vertices, motivated by network design
problems where junctions are significantly more expensive than simple end- or
through-nodes, and are thus to be avoided. We consider: $(\ast)$ connected
graphs on $n$ vertices such that $\sigma_2\ge n-k+1$ for some positive integer
$k$. In 1976, it was proved (by the author) that every graph satisfying
$(\ast)$ has a spanning tree with at most $k$ end vertices. In this paper we
first show that every graph satisfying $(\ast)$ has a spanning tree with at
most $k+1$ branch and end vertices altogether. The next result states that
every graph satisfying $(\ast)$ has a spanning tree with at most $(k-1)/2$
branch vertices. The third result states that every graph satisfying $(\ast)$
has a spanning tree with at most $\frac{3}{2}(k-1)$ degree sum of branch
vertices. All results are sharp.

37
The categories of this paper are: supr-con
20
The categories of this paper are: acc-phys
14
The categories of this paper are: math-ph
11
The categories of this paper are: hep-lat
19
The categories of this paper are: eess
6
The categories of this paper are: astro-ph
0
The categories of this paper are: hep-ph
13
The categories of this paper are: quant-ph
17
The categories of this paper are: q-fin
33
The categories of this paper are: plasm-ph
35
The categories of this paper are: mtrl-th
7
The categories of this paper are: hep-th
15
The categories of this paper are: nucl-ex
16
The categories of this paper are: stat
8
The categories of this paper are: hep-ex
23
The categories of this paper are: solv-int