The Cost of 2-Distinguishing Cartesian Powers
Author:
Open Access
- 7 January 2013
- journal article
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 20 (1) , P74
Abstract
A graph $G$ is said to be $2$-distinguishable if there is a labeling of the vertices with two labels so that only the trivial automorphism preserves the label classes. The minimum size of a label class in any such labeling of $G$ is called the cost of $2$-distinguishing $G$ and is denoted by $\rho(G)$. The determining number of a graph $G$, denoted $\det(G)$, is the minimum size of a set of vertices whose pointwise stabilizer is trivial. The main result of this paper is that if $G^k$ is a $2$-distinguishable Cartesian power of a prime, connected graph $G$ on at least three vertices with $\det(G)\leq k$ and $\max\{2, \det(G)\} < \det(G^k)$, then $\rho(G^k) \in \{\det(G^k), \det(G^k)+1\}$. In particular, for $n\geq 3$, $\rho(K_3^n)\in \{ \left\lceil {\log_3 (2n+1)} \right\rceil$ $+1, \left\lceil {\log_3 (2n+1)} \right\rceil$ $+2\}$.
Keywords
This publication has 5 references indexed in Scilit:
- The determining number of a Cartesian productJournal of Graph Theory, 2009
- Small label classes in 2-distinguishing labelingsArs Mathematica Contemporanea, 2008
- Cartesian powers of graphs can be distinguished by two labelsEuropean Journal of Combinatorics, 2007
- Distinguishing Cartesian powers of graphsJournal of Graph Theory, 2006
- Identifying Graph Automorphisms Using Determining SetsThe Electronic Journal of Combinatorics, 2006