Closure and spanning trees with bounded total excess
Closure and spanning trees with bounded total excess
复制标题
总超额有限的闭包树和生成树
DOI：
10.1007/s00373-021-02283-z
复制
发表时间：
2021
影响因子：
0.7
通讯作者：
Takamasa Yashima
中科院分区：
文献类型：
--
作者：
Shun-ichi Maezawa;Masao Tsugaki;Takamasa Yashima
设为整数。对于一个图G，G的总k-过剩定义为。在本文中，我们提出了一个新的封闭概念的生成树有界的总k-过剩。本文证明了：设G是一个连通图，且令和v是G的两个不相邻的顶点。如果G满足下列条件之一，则G有一个生成树T使得当且仅当G有一个生成树使得：（i）max { ∑ X ∈ X D G ( X ) : X 是 一 子集 的 S 与 | X | = K } ≥ | G | - 1 为 每 独立 设置 S 在 G 的 秩序 K + 1 等 的 { u , v } ⊆ S ;或（ii）最高 { ∑ X ∈ X D G ( X ) : X 是 一 子集 的 S 与 | X | = K } ≥ | G | - α - 1 为 每 独立 设置 S 在 G 的 秩序 K + α + 1 等 的 S ∩ { u , v } ≠ ∅ …
Letandbe integers. For a graphG, the totalk-excess ofGis defined as. In this paper, we propose a new closure concept for a spanning tree with bounded totalk-excess. We prove that: LetGbe a connected graph, and letuandvbe two non-adjacent vertices ofG. IfGsatisfies one of the following conditions, thenGhas a spanning treeTsuch thatif and only ifhas a spanning treesuch that:(i)max { ∑ x ∈ X d G ( x ) : X is a subset of S with | X | = k } ≥ | G | - 1 for every independent set S in G of order k + 1 such that { u , v } ⊆ S ; or(ii)max { ∑ x ∈ X d G ( x ) : X is a subset of S with | X | = k } ≥ | G | - α - 1 for every independent set S in G of order k + α + 1 such that S ∩ { u , v } ≠ ∅ …