On Distinguishing Graphs and Cost Number using Automorphism Representations Alexa Gopaulsingh ∗ , Zalán Molnár, Amitayu Banerjee

2025

Read On Distinguishing Graphs and Cost Number using Automorphism Representations Alexa Gopaulsingh ∗ , Zalán Molnár, Amitayu Banerjee (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-21299.txt.

Introduction

Alexa Gopaulsingh, Zalán Molnár, and Amitayu Banerjee bound the price of breaking a graph's symmetry in a 2025 paper. Color a graph's vertices so that only the trivial symmetry preserves the coloring, and the coloring is called distinguishing. The cost is the size of the smallest color class in a two-color distinguishing coloring. A related measure, the determining number, counts the fewest vertices whose fixing freezes every symmetry.

A standing question asked whether cost and determining number could drift arbitrarily far apart. For determining number one the answer was trivial; for two it stayed open. The authors close that case: with determining number two, the cost never exceeds four, a tight little bound. They also build families for every fixed determining number, giving lower bounds on how the price can grow. Symmetry, it turns out, cannot hide too cheaply.

Catalog record

YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE70 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-21299

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On Distinguishing Graphs and Cost Number using Automorphism Representations Alexa Gopaulsingh ∗ , Zalán Molnár, Amitayu Banerjee Abstract 2020 Mathematics Subject Classification 05C15, 05C25. Abstract A distinguishing coloring of a graph is a vertex coloring such that only the identity automorphism of the graph preserves the coloring. A 2-distinguishable graph is a graph which can be distinguished using 2 colors. The cost \rho(G) of a 2-distinguishable graph G , is the smallest size of a color set of a distinguishing coloring of G . The determining number of a graph G , Det(G) , is the minimum number of nodes, which if fixed by a coloring, would ensure that the coloring distinguishes the entire graph. Boutin (J. Combin. Math. Combin. Comput. 85: 161-171, 2013) posed an open problem which asks if \rho(G) and Det(G) can be arbitrarily far apart. It is trivial that it cannot be so for the case Det(G)=1 but the answer was unknown for Det(G)\geq 2 . We solve this problem for the case Det(G)=2 . We show that for the case Det(G)=2 , that not only is the cost bounded but in fact it takes small values with \rho(G)=2,\ 3 or 4 . In order to establish this, the concept of the automorphism representation of a graph is developed. Graphs having equivalent automorphism representations implies that they have the same distinguishing number (note that just having isomorphic automorphism groups is not enough for this to hold). This prompts a factoring of graphs by which two graphs are distinguishably equivalent iff they have equivalent automorphism representations. † † footnotetext: Keywords: distinguishing number, determining number, cost number, graph automorphisms aa 2020 Mathematics Subject Classification 05C15 05C25 aa *Corresponding author 1. Introduction The notion of distinguishing colorings was introduced in 1977 by László Babai under the name of asymmetric colorings, see [ 5 ] . This is a coloring of the nodes of a graph, not necessarily proper, such that only the identity automorphism preserves the coloring. Following this, in 1996, Albertson and Collins introduced in [ 3 ] , the distinguishing number of a graph G , D(G) , as the least integer d such that G admits a vertex coloring which is a distinguishing coloring of G with d colors. A graph that can be distinguished by a coloring using d colors is said to be d -distinguishable . There are several papers finding the distinguishing numbers of various classes of graphs, see Albertson and Boutin in [ 1 ] , Imrich and Klavzar in [ 15 ] , Tymoczko in [ 17 ] and Kalinowski and Pilśniak in [ 16 ] . The anecdotal setup introducing distinguishing colorings is one of seeing the nodes of a graph as identical looking keys placed in a graph structure. Then we can ask, what is the minimum number of colors needed to be able to tell which key is which? For example, if the keys are connected in a line by a string, we need two colors, say red and blue, to differentiate the keys on the different ends. In [ 7 ] , Boutin noticed that when 2-distinguishable graphs are considered, we can really use one color and consider the uncolored class the remaining color. In our chain of keys example, suppose that we have 10 keys or nodes. It is enough to only use red and color 3 keys red and now each key will have a unique place in this structure. The natural question, then became what is the minimum number of nodes that need to be painted in order to distinguish the graph, see [ 11 ] ? This type of question was originally posed by Wilfried Imrich, see [ 8 ] . Here, the definition of the cost number of a 2-distinguishable graph , \rho(G) , was given as the minimum number of nodes that needs to be colored to distinguish the graph, see Definition 3.1 . For the 10-node path in the given example, coloring 3 nodes red is wasting paint and it is enough to color 1 end node red to distinguish it for any P_{n} , where n\geq 2 . Interestingly, the difference between the number of nodes of the graph and cost can be vast. Boutin in [ 7 ] gave the example that the hypercube Q_{16} has 2^{16} vertices and 16!\times 2^{16} automorphisms, yet one only needs to color just 7 nodes red to distinguish it. For n\geq 5 , Boutin [ 7 , 10 ] showed that for hypercubes Q_{n} , \lceil log_{2}n\rceil+1\leq\rho(Q_{n})\leq 2\lceil log_{2}n\rceil-1 . Recent work shows that there are several classes of graphs that are 2-distinguishable. These classes include hypercubes Q_{n} , where n\geq 4 , see [ 6 ] ; Cartesian powers G^{n} of a connected graph G\neq K_{2},K_{3} , where n\geq 2 , see [ 15 ] ; Kneser graphs K_{n,k} , where n\geq 6 and k\geq 2 , see [ 2 ] ; and 3-connected planar graphs (excluding seven small graphs), see [ 13 ] . In fact, it is conjectured that almost all finite graphs are 2-distinguishable, see [ 16 ] . A significant concept used for finding the distinguishing and cost numbers of a graph, is the determining number of a graph G , denoted by Det(G) (see Definition 3.1 ). This is the minimum size of a set of nodes S , which is such that if \varphi is a non-trivial automorphism of G , then \varphi moves at least one node of S . This concept was also introduced in the literature as the fixing number of a set, see [ 12 ] , [ 14 ] . Alikhani and Soltani in [ 4 ] studied some properties of the cost numbers of graphs using their determining numbers. We know that for a fixed distinguishing number, we can find graphs with arbitrarly large determining number. Now, for graphs with Det(G)=1 , that is, only one node needs to be fixed to distinguish G , coloring that node red and everything else blue would be enough to distinguish this node and so its cost would also be 1. However, it was not clear what the cost could be if Det(G)\geq 2 , prompting Boutin to ask in [ 9 ] , the question: Open question : Find graphs for which \rho(G) is arbitrarily larger than Det(G) . We will show in this paper that if Det(G)=2 , then this is not possible (see Theorem 3.15 ). Indeed, not only is the cost bounded but in this case it takes small values and here \rho(G)=2,3 or 4, no matter how large G is. Note however, that the increase in difficulty of the solution from Det(G)=1 to Det(G)=2 is drastic as will be witnessed by the complexity of the proof required to establish the result. It is currently unknown what the situation is for Det(G)\geq 3 , even whether this condition bounds the cost in some cases and in others not. Moreover, if the bounds exist, then what are they? In Section 4, we use a class examples to obtain lower bounds on what the bounds of some further cases would be, if for these cases they do indeed exist. A

Read the complete text