On Well-Dominated Graphs
- PDF / 358,350 Bytes
- 15 Pages / 439.37 x 666.142 pts Page_size
- 26 Downloads / 209 Views
(0123456789().,-volV) (0123456789().,-volV)
ORIGINAL PAPER
On Well-Dominated Graphs Sarah E. Anderson1 • Kirsti Kuenzel2 • Douglas F. Rall3 Received: 21 September 2019 / Revised: 13 September 2020 / Accepted: 17 September 2020 Springer Japan KK, part of Springer Nature 2020
Abstract A graph is well-dominated if all of its minimal dominating sets have the same cardinality. It is proved that there are exactly eleven connected, well-dominated, triangle-free graphs whose domination number is at most 3. We prove that at least one of the factors is well-dominated if the Cartesian product of two graphs is welldominated. In addition, we show that the Cartesian product of two connected, triangle-free graphs is well-dominated if and only if both graphs are complete graphs of order 2. Under the assumption that at least one of the connected graphs G or H has no isolatable vertices, we prove that the direct product of G and H is welldominated if and only if either G ¼ H ¼ K3 or G ¼ K2 and H is either the 4-cycle or the corona of a connected graph. Furthermore, we show that the disjunctive product of two connected graphs is well-dominated if and only if one of the factors is a complete graph and the other factor has domination number at most 2. Keywords Well-dominated Well-covered Cartesian product Direct product Disjunctive product
Mathematics Subject Classification 05C69 05C76
& Douglas F. Rall [email protected] Sarah E. Anderson [email protected] Kirsti Kuenzel [email protected] 1
Department of Mathematics, University of St. Thomas, St. Paul, MN, USA
2
Department of Mathematics, Trinity College, Hartford, CT, USA
3
Department of Mathematics, Furman University, Greenville, SC, USA
123
Graphs and Combinatorics
1 Introduction Given a graph G and a positive integer k, deciding whether G has a dominating set of cardinality at most k is one of the classic NP-complete problems [5]. If we restrict the input graph to come from the class of well-dominated graphs (those graphs for which every minimal dominating set has the same cardinality), then this decision problem is solvable in linear time. The following simple procedure can be used to compute the order of a minimum dominating set in a well-dominated graph G. Let D ¼ VðGÞ. Choose any linear ordering of V(G) and process the vertices one at a time in this order. When a vertex v is processed, replace D by D fvg if D fvg dominates G. When all vertices in the sequence have been checked the resulting set D is a minimal (and hence minimum) dominating set of G. Since every maximal independent set of an arbitrary graph is also a minimal dominating set, one could also compute the domination number of a well-dominated graph by using a greedy algorithm to find a maximal independent set. The study of well-dominated graphs was initiated by Finbow, Hartnell and Nowakowski [4], and in that seminal paper they determined the well-dominated bipartite graphs as well as the structure of well-dominated graphs with no cycle of length less than 5. In [14] Topp and Vol
Data Loading...
