Star-uniform Graphs

Simple item page
dc.creatorKano, Mikio
dc.creatorWu, Yunjian
dc.creatorYu, Qinglin
dc.date2007-07-02
dc.date.accessioned2026-07-07T08:13:32Z
dc.date.available2026-07-07T08:13:32Z
dc.descriptionA {\it star-factor} of a graph $G$ is a spanning subgraph of $G$ such that each of its component is a star. Clearly, every graph without isolated vertices has a star factor. A graph $G$ is called {\it star-uniform} if all star-factors of $G$ have the same number of components. To characterize star-uniform graphs was an open problem posed by Hartnell and Rall, which is motivated by the minimum cost spanning tree and the optimal assignment problems. We use the concepts of factor-criticality and domination number to characterize all star-uniform graphs with the minimum degree at least two. Our proof is heavily relied on Gallai-Edmonds Matching Structure Theorem.
dc.identifierhttps://arxiv.org/abs/0707.0226
dc.identifierhttp://arxiv.org/abs/0707.0226
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/132801
dc.subjectCombinatorics
dc.subject05C69, 05C70
dc.titleStar-uniform Graphs
dc.typetext

Files

Collections

arXiv