Christopher Coscia ; Jonathan DeWitt ; Fan Yang ; Yiguang Zhang - Best and worst case permutations for random online domination of the path

dmtcs:3278 - Discrete Mathematics & Theoretical Computer Science, December 20, 2017, Vol. 19 no. 2, Permutation Patterns 2016 - https://doi.org/10.23638/DMTCS-19-2-2
Best and worst case permutations for random online domination of the path

Authors: Christopher Coscia ; Jonathan DeWitt ; Fan Yang ; Yiguang Zhang

    We study a randomized algorithm for graph domination, by which, according to a uniformly chosen permutation, vertices are revealed and added to the dominating set if not already dominated. We determine the expected size of the dominating set produced by the algorithm for the path graph $P_n$ and use this to derive the expected size for some related families of graphs. We then provide a much-refined analysis of the worst and best cases of this algorithm on $P_n$ and enumerate the permutations for which the algorithm has the worst-possible performance and best-possible performance. The case of dominating the path graph has connections to previous work of Bouwer and Star, and of Gessel on greedily coloring the path.


    Volume: Vol. 19 no. 2, Permutation Patterns 2016
    Section: Permutation Patterns
    Published on: December 20, 2017
    Accepted on: December 20, 2017
    Submitted on: April 21, 2017
    Keywords: Mathematics - Combinatorics

    Share

    Consultation statistics

    This page has been seen 378 times.
    This article's PDF has been downloaded 184 times.