Best and worst case permutations for random online domination of the path

• DOI: 10.23638/dmtcs-19-2-2
• Publication Date: 2025-04-03T16:42:54Z
• Authors: Christopher Coscia; Jonathan DeWitt; Fan Yang; Yiguang Zhang
• Keywords: mathematics - combinatorics; QA1-939; FOS: Mathematics; Mathematics - Combinatorics; Combinatorics (math.CO); 0102 computer and information sciences; 16. Peace & justice; 01 natural sciences; Mathematics

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