The cost of 2-distinguishing Cartesian powers
type: Item
instance of: scholarly article
title: The cost of 2-distinguishing Cartesian powers
zbMATH Open document ID: 1266.05138
published in: The Electronic Journal of Combinatorics
publication date: 2013-06-07T00:00:00Z
full work available at URL: v20i1p74
review text: Summary: 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\}\).
Mathematics Subject Classification ID: 05C78
Mathematics Subject Classification ID: 05C25
zbMATH DE Number: 6171913
zbMATH Keywords: Cartesian product
zbMATH Keywords: graph distinguishing
zbMATH Keywords: determining number
author: Debra L. Boutin
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 6171913