Edge-disjoint spanning trees and the number of maximum state circles of a graph
Edge-disjoint spanning trees and the number of maximum state circles of a graph
复制标题
边不相交的生成树和图的最大状态圈数
DOI：
10.1007/s10878-018-0249-y
复制
发表时间：
2018
影响因子：
1
通讯作者：
Jin Xian'an
中科院分区：
文献类型：
--
作者：
Ma Xiaoli;Wu Baoyindureng;Jin Xian'an
受无向交替环属的启发，Jin等人（Acta Math Appl Sin Engl Ser，2015）引入了平面图G的最大状态圈数，记为，并证明了H是的生成子图，其中，e（H），c（H）和v（H）分别表示H的大小，连通分支数和阶。在本文中，我们表明，任何（不一定是平面）图G，可以实现的生成子图H的G，其每个连通组件是一个极大子图的G与两个边不相交的生成树。证明了这样一个生成子图是唯一的，并给出了一个多项式时间算法来求任意图G的这样一个生成子图。
Motivated by the connection with the genus of unoriented alternating links, Jin et al. (Acta Math Appl Sin Engl Ser, 2015) introduced the number of maximum state circles of a plane graphG, denoted by, and proved thatHis a spanning subgraph of, wheree(H),c(H) andv(H) denote the size, the number of connected components and the order ofH, respectively. In this paper, we show that for any (not necessarily planar) graphG,can be achieved by the spanning subgraphHofGwhose each connected component is a maximal subgraph ofGwith two edge-disjoint spanning trees. Such a spanning subgraph is proved to be unique and we present a polynomial-time algorithm to find such a spanning subgraph for any graphG.