The cost of 2-distinguishing hypercubes
| Autor: | Debra L. Boutin |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Discrete mathematics
020206 networking & telecommunications 0102 computer and information sciences 02 engineering and technology Automorphism 01 natural sciences Theoretical Computer Science Combinatorics Integer 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering Discrete Mathematics and Combinatorics Hypercube Mathematics |
| Zdroj: | Discrete Mathematics. 344:112512 |
| ISSN: | 0012-365X |
| DOI: | 10.1016/j.disc.2021.112512 |
| Popis: | 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 labels. The minimum size of a label class, over all 2-distinguishing labelings, is called the cost of 2-distinguishing, denoted by ρ ( G ) . For n ≥ 4 the hypercubes Q n are 2-distinguishable, but the values for ρ ( Q n ) have been elusive, with only bounds and partial results previously known. This paper settles the question. The main result can be summarized as: for n ≥ 4 , ρ ( Q n ) ∈ { 1 + ⌈ log 2 n ⌉ , 2 + ⌈ log 2 n ⌉ } . Exact values are found using a recursive relationship involving a new parameter ν m , the smallest integer for which ρ ( Q ν m ) = m . The main result is 4 ≤ n ≤ 12 ⟹ ρ ( Q n ) = 5 , and 5 ≤ m ≤ 11 ⟹ ν m = 4 ; for m ≥ 6 , ρ ( Q n ) = m ⇔ 2 m − 2 − ν m − 1 + 1 ≤ n ≤ 2 m − 1 − ν m ; for n ≥ 5 , ν m = n ⇔ 2 n − 1 − ρ ( Q n − 1 ) + 1 ≤ m ≤ 2 n − ρ ( Q n ) . |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect