Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/s00373-010-0917-x | Graphs and Combinatorics |
Keywords | Field | DocType |
star-uniform graphs,domination number,open problem,gallai-edmonds decomposition,deploying gallai,star-unform graph,matching number,factor-criticality,minimum cost,complete characterization,star-factor,edmonds matching structure theorem,star-uniform graph,graph g,star-uniform,equal domination,assignment problem,spanning tree | Topology,Discrete mathematics,Indifference graph,Combinatorics,Tree-depth,Forbidden graph characterization,Graph factorization,Chordal graph,Cograph,Pathwidth,Mathematics,Split graph | Journal |
Volume | Issue | ISSN |
26 | 3 | 1435-5914 |
Citations | PageRank | References |
0 | 0.34 | 6 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mikio Kano | 1 | 548 | 99.79 |
| Yunjian Wu | 2 | 2 | 0.87 |
| Qinglin Yu | 3 | 102 | 20.73 |