We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
DETERMINING NUMBER AND COST OF GENERALIZED MYCIELSKIAN GRAPHS.
- Authors
BOUTIN, DEBRA; COCKBURN, SALLY; KEOUGH, LAUREN; LOEB, SARAH; PERRY, K. E.; ROMBACH, PUCK
- Abstract
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 6= K2 is twin-free with no isolated vertices, then Det(μt(G)) = Det(G). 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).
- Subjects
K2 (Pakistan : Mountain); COST; COLORS; DOMINATING set; COLOR; COLORING matter
- Publication
Discussiones Mathematicae: Graph Theory, 2024, Vol 44, Issue 1, p127
- ISSN
1234-3099
- Publication type
Article
- DOI
10.7151/dmgt.2438