Algorithms for secondary domination. (English) Zbl 1206.05075

Summary: At the 39th Southeastern International Conference on Combinatorics, Game Theory, and Computing, S. T. Hedetniemi introduced the idea of secondary domination denoted \(\gamma(m,n)\), where \(m\) and \(n\) are positive integers and \(m\leq n\). (See also [S.M. Hedetnemi, S.T. Hedetniemi, J. Knisely, and D.F. Rall, “Secondary dominaton in raphs,” AKCE Int. J. Graphs Comb. 5, No.2, 103–115 (2008; Zbl 1176.05055)].) This concept concerns the location of the second member of the set from the perspective of vertices not in the set. Many subset parameters can be described utilizing secondary domination. For instance, distance-two double domination is one subset parameter that can be described as a \(\gamma(2,2)\) parameter. We present a Wimer-style algorithm for \(\gamma(2,2)\) as well as observations made during the exploration of the relationship between \(\gamma(1,3)\) and \(\gamma(2,2)\).


05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C85 Graph algorithms (graph-theoretic aspects)


Zbl 1176.05055