Determining number and cost of generalized Mycielskian graphs
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 1, pp. 127-150
Voir la notice de l'article provenant de la source Library of Science
A set S of vertices is a determining set for a graph G if every automorphism of G is uniquely determined by its action on S and Det(G) is the size of smallest determining set of G. A graph G is d-distinguishable if there is a coloring of the vertices with d colors so that only the trivial automorphism preserves the color classes and Dist(G) is the smallest d for which G is d-distinguishable. If Dist(G) = 2, the cost of 2-distinguishing, ρ(G), is the size of a smallest color class over all 2-distinguishing colorings of G. This paper examines the determining number and, when relevant, the cost of 2-distinguishing for Mycielskians μ(G) and generalized Mycielskians μ_t(G) of simple graphs with no isolated vertices. In particular, if G K_2 is twin-free with no isolated vertices, then Det(μ_t(G)) = DetG). If in addition Det(G) ≥ 2 and t≥Det(G)-1, then Dist(μ_t(G))=2 and ρ(μ_t(G)) = Det(G). For G with twins, we develop a framework using quotient graphs to find Det(μ(G)) and Det(μ_t(G)) in terms of Det(G).
Keywords:
determining number, graph distinguishing, cost of 2-distinguishing, Mycielskian graph
@article{DMGT_2024_44_1_a6,
author = {Boutin, Debra and Cockburn, Sally and Keough, Lauren and Loeb, Sarah and Perry, K.E. and Rombach, Puck},
title = {Determining number and cost of generalized {Mycielskian} graphs},
journal = {Discussiones Mathematicae. Graph Theory},
pages = {127--150},
publisher = {mathdoc},
volume = {44},
number = {1},
year = {2024},
language = {en},
url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a6/}
}
TY - JOUR AU - Boutin, Debra AU - Cockburn, Sally AU - Keough, Lauren AU - Loeb, Sarah AU - Perry, K.E. AU - Rombach, Puck TI - Determining number and cost of generalized Mycielskian graphs JO - Discussiones Mathematicae. Graph Theory PY - 2024 SP - 127 EP - 150 VL - 44 IS - 1 PB - mathdoc UR - http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a6/ LA - en ID - DMGT_2024_44_1_a6 ER -
%0 Journal Article %A Boutin, Debra %A Cockburn, Sally %A Keough, Lauren %A Loeb, Sarah %A Perry, K.E. %A Rombach, Puck %T Determining number and cost of generalized Mycielskian graphs %J Discussiones Mathematicae. Graph Theory %D 2024 %P 127-150 %V 44 %N 1 %I mathdoc %U http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a6/ %G en %F DMGT_2024_44_1_a6
Boutin, Debra; Cockburn, Sally; Keough, Lauren; Loeb, Sarah; Perry, K.E.; Rombach, Puck. Determining number and cost of generalized Mycielskian graphs. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 1, pp. 127-150. http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a6/