Star-Uniform Graphs

摘要

A star-factor of a graph is a spanning subgraph each of whose components is a star. A graph G is called star-uniform if all star-factors of G have the same number of components. Motivated by the minimum cost spanning tree and the optimal assignment problems, Hartnell and Rall posed an open problem to characterize all the star-uniform graphs. In this paper, we show that a graph G is star-uniform if and only if G has equal domination and matching number. From this point of view, the star-uniform graphs were characterized by Randerath and Volkmann. Unfortunately, their characterization is incomplete. By deploying Gallai–Edmonds Matching Structure Theorem, we give a clear and complete characterization of star-unform graphs.