# Symmetry breaking indices for the Cartesian product of graphs

@inproceedings{Alikhani2021SymmetryBI, title={Symmetry breaking indices for the Cartesian product of graphs}, author={Saeid Alikhani and Mohammad Hadi Shekarriz}, year={2021} }

A vertex coloring is called distinguishing if the identity is the only automorphism that can preserve it. The distinguishing number of a graph is the minimum number of colors required for such a coloring. The distinguishing threshold of a graph G is the minimum number of colors k required that any arbitrary k-coloring of G is distinguishing. We prove a statement that gives a necessary and sufficient condition for a vertex coloring of the Cartesian product to be distinguishing. Then we use it to… Expand

#### One Citation

Breaking symmetries of some graph operations by vertex coloring

- Mathematics
- 2021

A vertex coloring of a graph G is distinguishing if any non-identity automorphism of G does not preserve it. The distinguishing number is the minimum number of colors required for such a coloring and… Expand

#### References

SHOWING 1-10 OF 19 REFERENCES

The distinguishing number of Cartesian products of complete graphs

- Computer Science, Mathematics
- Eur. J. Comb.
- 2008

The distinguishing number D(G) of a graph G is the least integer d such that G has a labeling with d labels that is preserved only by a trivial automorphism. We prove that Cartesian products of… Expand

Distinguishing Cartesian Products of Countable Graphs

- Mathematics, Computer Science
- Discuss. Math. Graph Theory
- 2017

Results about the distinguishing number of Cartesian products of finite and infinite graphs are improved by removing restrictions to prime or relatively prime factors. Expand

Number of distinguishing colorings and partitions

- Mathematics, Computer Science
- Discret. Math.
- 2020

If one knows the distinguishing threshold of a graph $G$, which is the smallest number of colors $\theta(G)$ so that, for $k\geq \theta (G)$, every $k$-coloring of $G$ is distinguishing, then, in some special cases, counting the number of distinguishing colorings with $k $ colors is vary easy. Expand

Distinguishing Cartesian powers of graphs

- Computer Science
- J. Graph Theory
- 2006

It is shown that the distinguishing number of the square and higher powers of a connected graph G 6= K2,K3 with respect to the Cartesian product is 2 and d(G¤H) = 2 if G and H are relatively prime. Expand

Distinguishing colorings of Cartesian products of complete graphs

- Computer Science, Mathematics
- Discret. Math.
- 2008

The values of s and t for which there is a coloring of the edges of the complete bipartite graph K"s","t" which admits only the identity automorphism are determined to determine the distinguishing number of the Cartesian product of complete graphs. Expand

Distinguishing graphs by edge-colourings

- Mathematics, Computer Science
- Eur. J. Comb.
- 2015

It follows that each connected Class 2 graph G admits a minimal proper edge-colouring, i.e., with χ ′ ( G ) colours, preserved only by the trivial automorphism. Expand

The Distinguishing Chromatic Number

- Mathematics, Computer Science
- Electron. J. Comb.
- 2006

In this paper we define and study the distinguishing chromatic number, $\chi_D(G)$, of a graph $G$, building on the work of Albertson and Collins who studied the distinguishing number. We find… Expand

Distinguishing graphs by total colourings

- Mathematics, Computer Science
- Ars Math. Contemp.
- 2016

Sharp upper bounds are set for the minimal number of colours in a proper total colouring such that each vertex has a distinct set of colour walks emanating from it. Expand

Symmetry Breaking in Graphs

- Mathematics, Computer Science
- Electron. J. Comb.
- 1996

The distinguishing number of a graph G, denoted by D(G), is the minimum r such that G has an r-distinguishing labeling, and the distinguishingNumber of the complete graph on t vertices is t. Expand

Handbook of Product Graphs, Second Edition

- Mathematics
- 2011

Handbook of Product Graphs, Second Edition examines the dichotomy between the structure of products and their subgraphs. It also features the design of efficient algorithms that recognize products… Expand