Article in volume
Authors:
Title:
Determining number and cost of generalized Mycielskian graphs
PDFSource:
Discussiones Mathematicae Graph Theory 44(1) (2024) 127-150
Received: 2021-04-30 , Revised: 2021-10-27 , Accepted: 2021-10-29 , Available online: 2021-11-17 , https://doi.org/10.7151/dmgt.2438
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 %said to be
$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, $\rho(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 $\mu(G)$ and generalized Mycielskians $\mu_t(G)$
of simple graphs with no isolated vertices. In particular, if $G \neq K_2$ is
twin-free with no isolated vertices, then $\det(\mu_t(G)) = \det(G)$. If in
addition $\det(G) \geq 2$ and $t\ge \det(G)-1$, then Dist$(\mu_t(G))=2$ and
$\rho(\mu_t(G)) = \det(G)$. For $G$ with twins, we develop a framework using
quotient graphs to find $\det(\mu(G))$ and $\det(\mu_t(G))$ in terms of $\det(G)$.
Keywords:
determining number, graph distinguishing, cost of 2-distinguishing, Mycielskian graph
References:
- A. Mohammed Abid and T.R. Ramesh Rao, Dominator coloring of Mycielskian graphs, Australas. J. Combin. 73 (2019) 274–279.
- M.O. Albertson, Distinguishing Cartesian powers of graphs, Electron. J. Combin. 12 (2005) #N17.
https://doi.org//10.37236/1984 - 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 - M.O. Albertson and K.L. Collins, Symmetry breaking in graphs, Electron. J. Combin. 3(1) (1996) #R18.
https://doi.org/10.37236/1242 - 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 - L. Babai, Asymmetric trees with two prescribed degrees, Acta Math. Acad. Sci. Hungar. 29 (1977) 193–200.
https://doi.org/10.1007/BF01896481 - 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 - 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.
- 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 - D. Boutin, S. Cockburn, L. Keough, S. Loeb, K.E. Perry and P. Rombach, Distinguishing generalized Mycielskian graphs (2020).
arXiv: 2006.03739 - 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 - 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 - D. Boutin, Identifying graph automorphisms using determining sets, Electron. J. Combin. 13 (2006) #R78.
https://doi.org/10.37236/1104 - 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 - D. Boutin, The determining number of a Cartesian product, J. Graph Theory 61 (2009) 77–87.
https://doi.org/10.1002/jgt.20368 - D. Boutin, The cost of $2$-distinguishing Cartesian powers, Electron. J. Combin. 20 (2013) #P74.
https://doi.org/10.37236/3223 - D. Boutin, The cost of $2$-distinguishing selected Kneser graphs and hypercubes, J. Combin. Math. Combin. Comput. 85 (2013) 161–171.
- X.G. Chen and H.-M. Xing, Domination parameters in Mycielski graphs, Util. Math. 71 (2006) 235–244.
- 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 - W. Imrich, (2007), personal communication.
- 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 - W. Imrich, S. Klavžar and V. Trofimov, Distinguishing infinite graphs, Electron. J. Combin. 14 (2007) #R36.
https://doi.org/10.37236/954 - 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 - 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 - J. Mycielski, Sur le coloriage des graphs, Colloq. Math. 3 (1955) 161–162.
https://doi.org/10.4064/cm-3-2-161-162 - Z. Pan and X. Zhu, Multiple coloring of cone graphs, SIAM J. Discrete Math. 24 (2010) 1515–1526.
https://doi.org/10.1137/070691486 - 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 - M. Stiebitz, Beiträge zur Theorie der färbungskritischen Graphen, PhD Thesis (Technical University Ilmenau, 1985).
- C. Tardif, Fractional chromatic numbers of cones over graphs, J. Graph Theory 38 (2001) 87–94.
https://doi.org/10.1002/jgt.1025 - N. Van Ngoc, On Graph Colourings, PhD Thesis (Hungarian Academy of Sciences, 1987).
- 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
Close