Geodesic
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/