Geodesic
Determining number and cost of generalized Mycielskian graphs
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 1, pp. 127-150 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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},
     year = {2024},
     volume = {44},
     number = {1},
     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
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
%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/

[1] A. Mohammed Abid and T.R. Ramesh Rao, Dominator coloring of Mycielskian graphs, Australas. J. Combin. 73 (2019) 274–279.

[2] M.O. Albertson, Distinguishing Cartesian powers of graphs, Electron. J. Combin. 12 (2005) #N17. https://doi.org//10.37236/1984

[3] M.O. Albertson and D.L. Boutin, Using determining sets to distinguish Kneser graphs, Electron. J. Combin. 14 (2007) #R20. https://doi.org/10.37236/938

[4] M.O. Albertson and K.L. Collins, Symmetry breaking in graphs, Electron. J. Combin. 3(1) (1996) #R18. https://doi.org/10.37236/1242

[5] S. Alikhani and S. Soltani, Symmetry breaking in planar and maximal outerplanar graphs, Discrete Math. Algorithms Appl. 11 (2019) 1950008. https://doi.org/10.1142/S1793830919500083

[6] L. Babai, Asymmetric trees with two prescribed degrees, Acta Math. Acad. Sci. Hungar. 29 (1977) 193–200. https://doi.org/10.1007/BF01896481

[7] R. Balakrishnan and S. Francis Raj, Connectivity of the Mycielskian of a graph, Discrete Math. 308 (2008) 2607–2610. https://doi.org/10.1016/j.disc.2007.05.004

[8] R. Balakrishnan and S. Francis Raj, Bounds for the b-chromatic number of the Mycielskian of some families of graphs, Ars Combin. 122 (2015) 89–96.

[9] B. Bogstad and L.J. Cowen, The distinguishing number of the hypercube, Discrete Math. 283 (2004) 29–35. https://doi.org/10.1016/j.disc.2003.11.018

[10] D. Boutin, S. Cockburn, L. Keough, S. Loeb, K.E. Perry and P. Rombach, Distinguishing generalized Mycielskian graphs (2020). arXiv: 2006.03739

[11] D. Boutin, S. Cockburn, L. Keough, S. Loeb, K.E. Perry and P. Rombach, Symmetry parameters for Mycielskian graphs, in: Research Trends in Graph Theory and Applications, Assoc. Women Math. Ser. 25, (2021 Springer International Publishing) 96–117. https://doi.org/10.1007/978-3-030-77983-2_5

[12] D. Boutin and W. Imrich, The cost of distinguishing graphs, in: Groups, Graphs and Random Walks, London Math. Soc. Lecture Note Ser. 436, (Cambridge Univ. Press, Cambridge 2017) 104–119. https://doi.org/10.1017/9781316576571.005

[13] D. Boutin, Identifying graph automorphisms using determining sets, Electron. J. Combin. 13 (2006) #R78. https://doi.org/10.37236/1104

[14] D. Boutin, Small label classes in 2-distinguishing labelings, Ars Math. Contemp. 1 (2008) 154–164. https://doi.org/10.26493/1855-3974.31.d93

[15] D. Boutin, The determining number of a Cartesian product, J. Graph Theory 61 (2009) 77–87. https://doi.org/10.1002/jgt.20368

[16] D. Boutin, The cost of 2-distinguishing Cartesian powers, Electron. J. Combin. 20 (2013) #P74. https://doi.org/10.37236/3223

[17] D. Boutin, The cost of 2-distinguishing selected Kneser graphs and hypercubes, J. Combin. Math. Combin. Comput. 85 (2013) 161–171.

[18] X.G. Chen and H.-M. Xing, Domination parameters in Mycielski graphs, Util. Math. 71 (2006) 235–244.

[19] D.C. Fisher, P.A. McKenna and E.D. Boyer, Hamiltonicity, diameter, domination, packing, and biclique partitions of Mycielski's graphs, Discrete Appl. Math. 84 (1998) 93–105. https://doi.org/10.1016/S0166-218X(97)00126-1

[20] W. Imrich, (2007), personal communication.

[21] W. Imrich and S. Klavžar, Distinguishing Cartesian powers of graphs, J. Graph Theory 53 (2006) 250–260. https://doi.org/10.1002/jgt.20190

[22] W. Imrich, S. Klavžar and V. Trofimov, Distinguishing infinite graphs, Electron. J. Combin. 14 (2007) #R36. https://doi.org/10.37236/954

[23] S. Klavžar and X. Zhu, Cartesian powers of graphs can be distinguished by two labels, European J. Combin. 28 (2007) 303–310. https://doi.org/10.1016/j.ejc.2005.07.001

[24] W. Lin, J. Wu, P.C.B. Lam and G. Gu, Several parameters of generalized Mycielskians, Discrete Appl. Math. 154 (2006) 1173–1182. https://doi.org/10.1016/j.dam.2005.11.001

[25] J. Mycielski, Sur le coloriage des graphs, Colloq. Math. 3 (1955) 161–162. https://doi.org/10.4064/cm-3-2-161-162

[26] Z. Pan and X. Zhu, Multiple coloring of cone graphs, SIAM J. Discrete Math. 24 (2010) 1515–1526. https://doi.org/10.1137/070691486

[27] S.M. Smith, T.W. Tucker and M.E. Watkins, Distinguishability of infinite groups and graphs, Electron. J. Combin. 19 (2012) #P27. https://doi.org/10.37236/2283

[28] M. Stiebitz, Beiträge zur Theorie der färbungskritischen Graphen, PhD Thesis (Technical University Ilmenau, 1985).

[29] C. Tardif, Fractional chromatic numbers of cones over graphs, J. Graph Theory 38 (2001) 87–94. https://doi.org/10.1002/jgt.1025

[30] N. Van Ngoc, On Graph Colourings, PhD Thesis (Hungarian Academy of Sciences, 1987).

[31] N. Van Ngoc and Zs. Tuza, 4-chromatic graphs with large odd girth, Discrete Math. 138 (1995) 387–392. https://doi.org/10.1016/0012-365X(94)00221-4