科研之友
微信
新浪微博
Facebook
分享链接
摘要
A star-factor of a graph G is a spanning subgraph of G such that each component is a star. An edge-weighting of G is a function w : E(G) -> N+, where N+ is the set of positive integers. Let Omega be the family of all graphs G such that every star-factor of G has the same weight under some fixed edge-weighting w. The open problem of characterizing the class Omega, posed by Hartnell and Rail, is motivated by the minimum cost spanning tree and the optimal assignment problems. In this paper, we present a simple structural characterization of the graphs in Omega that have girth at least five.
- 出版日期2014-1
- 单位南开大学
