Uniformly Weighted Star-Factors of Graphs

Abstract

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) \rightarrow \mathbb{N}^+\), where \(\mathbb{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 Rall, 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.