Closure and Spanning Trees with Bounded Total Excess
2021
Let $$\alpha \ge 0$$
and $$k \ge 2$$
be integers. For a graph G, the total k-excess of G is defined as $$\text{ te }(G;k)=\sum _{v \in V(G)}\max \{d_G(v)-k,0\}$$
. In this paper, we propose a new closure concept for a spanning tree with bounded total k-excess. We prove that: Let G be a connected graph, and let u and v be two non-adjacent vertices of G. If G satisfies one of the following conditions, then G has a spanning tree T such that $$\text{ te }(T;k) \le \alpha$$
if and only if $$G+uv$$
has a spanning tree $$T'$$
such that $$\text{ te }(T';k) \le \alpha$$
: We also show examples to show that these conditions are sharp.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
11
References
0
Citations
NaN
KQI