1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

Determining Number and Cost of Generalized Mycielskian Graphs

Published Online: 26 Nov 2021
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 30 Apr 2021
Accepted: 29 Oct 2021
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

A set S of vertices is a determining set for a graph G if every auto-morphism 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 GK2 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).

Keywords

MSC 2010

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

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

[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/93810.37236/938 Search in Google Scholar

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

[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/S179383091950008310.1142/S1793830919500083 Search in Google Scholar

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

[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.00410.1016/j.disc.2007.05.004 Search in Google Scholar

[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. Search in Google Scholar

[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.01810.1016/j.disc.2003.11.018 Search in Google Scholar

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

[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_510.1007/978-3-030-77983-2_5 Search in Google Scholar

[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.00510.1017/9781316576571.005 Search in Google Scholar

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

[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.d9310.26493/1855-3974.31.d93 Search in Google Scholar

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

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

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

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

[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-110.1016/S0166-218X(97)00126-1 Search in Google Scholar

[20] W. Imrich (2007), personal communication. Search in Google Scholar

[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.2019010.1002/jgt.20190 Search in Google Scholar

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

[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.00110.1016/j.ejc.2005.07.001 Search in Google Scholar

[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.00110.1016/j.dam.2005.11.001 Search in Google Scholar

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

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

[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/228310.37236/2283 Search in Google Scholar

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

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

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

[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-410.1016/0012-365X(94)00221-4 Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo