Ratio Mathematica Volume 31, 2019, pp. 79-88

The distinguishing number and the
distinguishing index of co-normal product

of two graphs

Saeid Alikhani∗

Samaneh Soltani †

Abstract

The distinguishing number (index) D(G) (D′(G)) of a graph G is
the least integer d such that G has an vertex labeling (edge labeling)
with d labels that is preserved only by a trivial automorphism. The
co-normal product G ? H of two graphs G and H is the graph with
vertex set V (G) × V (H) and edge set {{(x1,x2),(y1,y2)}|x1y1 ∈
E(G) or x2y2 ∈ E(H)}. In this paper we study the distinguishing
number and the distinguishing index of the co-normal product of two
graphs. We prove that for every k ≥ 3, the k-th co-normal power
of a connected graph G with no false twin vertex and no dominating
vertex, has the distinguishing number and the distinguishing index
equal two.
Keywords: distinguishing number; distinguishing index; co-normal
product.
2010 AMS subject classifications: 05C15, 05C60. 1

∗Department of Mathematics, Yazd University, Yazd, Iran; alikhani@yazd.ac.ir
†Department of Mathematics, Yazd University, Yazd, Iran; s.soltani1979@gmail.com
1Received on February 12th, 2019. Accepted on May 3rd, 2019. Published on June 30th, 2019.

doi: 10.23755/rm.v36i1.452. ISSN: 1592-7415. eISSN: 2282-8214. c©Alikhani and Soltani.
This paper is published under the CC-BY licence agreement.

79



Saeid Alikhani, Samaneh Soltani

1 Introduction and definitions
Let G = (V,E) be a simple graph of order n ≥ 2. We use the the following

notations: The set of vertices adjacent in G to a vertex of a vertex subset W ⊆ V
is the open neighborhood N(W) of W . Also N(W) ∪ W is called a closed
neighborhood of W and denoted by N[W ]. A subgraph of a graph G is a graph
H such that V (H) ⊆ V (G) and E(H) ⊆ E(G). If V (H) = V (G), we call
H a spanning subgraph of G. Any spanning subgraph of G can be obtained by
deleting some of the edges from G. Two distinct vertices u and v are called true
twins if N[v] = N[u] and false twins if N(v) = N(u). Two vertices are called
twins if they are true or false twins. The number |N(v)| is called the degree of v
in G, denoted as degG(v) or deg(v). A vertex having degree |V (G)|−1 is called
a dominating vertex of G. Also, Aut(G) denotes the automorphism group of G,
and graphs with |Aut(G)| = 1 are called rigid graphs.

A labeling of G, φ : V → {1,2, . . . ,r}, is said to be r-distinguishing, if no
non-trivial automorphism of G preserves all of the vertex labels. The point of the
labels on the vertices is to destroy the symmetries of the graph, that is, to make the
automorphism group of the labeled graph trivial. Formally, φ is r-distinguishing
if for every non-trivial σ ∈ Aut(G), there exists x in V such that φ(x) 6= φ(σ(x)).
The distinguishing number of a graph G is defined by

D(G) = min{r| G has a labeling that is r-distinguishing}.

This number has defined in [1]. Similar to this definition, the distinguishing
index D′(G) of G has defined in [8] which is the least integer d such that G has
an edge colouring with d colours that is preserved only by a trivial automorphism.
If a graph has no nontrivial automorphisms, its distinguishing number is 1. In
other words, D(G) = 1 for the asymmetric graphs. The other extreme, D(G) =
|V (G)|, occurs if and only if G is a complete graph. The distinguishing index of
some examples of graphs was exhibited in [8]. For instance, D(Pn) = D′(Pn) = 2
for every n ≥ 3, and D(Cn) = D′(Cn) = 3 for n = 3,4,5, D(Cn) = D′(Cn) =
2 for n ≥ 6, where Pn denotes a path graph on n vertices and Cn denotes a
cycle graph on n vertices. A graph and its complement, always have the same
automorphism group while their graph structure usually differs, hence D(G) =
D(G) for every simple graph G.

Product graph of two graphs G and H is a new graph having the vertex set
V (G) × V (H) and the adjacency of vertices is defined under some rule using
the adjacency and the nonadjacency relations of G and H. The distinguishing
number and the distinguishing index of some graph products has been studied in
literature (see [2, 6, 7]). The Cartesian product of graphs G and H is a graph,
denoted by G2H, whose vertex set is V (G) × V (H). Two vertices (g,h) and
(g′,h′) are adjacent if either g = g′ and hh′ ∈ E(H), or gg′ ∈ E(G) and h = h′.

80



The distinguishing number and the distinguishing index of co-normal product of
two graphs

In 1962, Ore [10] introduced a product graph, with the name Cartesian sum of
graphs. Hammack et al. [4], named it co-normal product graph. The co-normal
product of G and H is the graph denoted by G ? H, and is defined as follows:

V (G ? H) = {(g,h)|g ∈ V (G) and h ∈ V (H)},
E(G ? H) = {{(x1,x2),(y1,y2)}|x1y1 ∈ E(G) or x2y2 ∈ E(H)}.

We need knowledge of the structure of the automorphism group of the Carte-
sian product, which was determined by Imrich [5], and independently by Miller
[9].

Theorem 1.1. [5, 9] Suppose ψ is an automorphism of a connected graph G with
prime factor decomposition G = G12G22 . . .2Gr. Then there is a permutation
π of the set {1,2, . . . ,r} and there are isomorphisms ψi : Gπ(i) → Gi, i =
1, . . . ,r, such that

ψ(x1,x2, . . . ,xr) = (ψ1(xπ(1)),ψ2(xπ(2)), . . . ,ψr(xπ(r))).

Imrich and Klavžar in [7], and Gorzkowska et.al. in [3] showed that the dis-
tinguishing number and the distinguishing index of the square and higher powers
of a connected graph G 6= K2,K3 with respect to the Cartesian product is 2.

The relationship between the automorphism group of co-normal product of
two non isomorphic, non rigid connected graphs with no false twin and no domi-
nating vertex is the same as that in the case of the Cartesian product.

Theorem 1.2. [12] For any two non isomorphic, non rigid graphs G and H,
Aut(G?H) = Aut(G)×Aut(H) if and only if both G and H have no false twins
and dominating vertices.

Theorem 1.3. [12] For any two rigid isomorphic graphs G and H, Aut(G?H) ∼=
S2.

Theorem 1.4. [12]The graph G?H is rigid if and only if G � H and both G and
H are rigid graphs.

In the next section, we study the distinguishing number of the co-normal prod-
uct of two graphs. In section 3, we show that the distinguishing index of the co-
normal product of two simple connected non isomorphic, non rigid graphs with
no false twin and no dominating vertex cannot be more than the distinguishing
index of their Cartesian product. As a consequence, we prove that all powers of a
connected graph G with no false twin and no dominating vertex distinguished by
exactly two edge labels with respect to the co-normal product.

81



Saeid Alikhani, Samaneh Soltani

2 Distinguishing number of co-normal product of
two graphs

We begin this section with a general upper bound for the co-normal product
of two simple connected graphs. We need the following theorem.

Theorem 2.1. [12] Let G and H be two graphs and λ : V (G ? H) → V (G ? H)
be a mapping.

(i) If λ = (α,β) defined as λ(g,h) = (α(g),β(h)), where α ∈ Aut(G) and
β ∈ Aut(H), then λ is an automorphism on G ? H.

(ii) If G is isomorphic to H and λ = (α,β) defined as λ(g,h) = (β(h),α(g)),
where α is an isomorphism on G to H and β is an isomorphism on H to G,
then λ is an automorphism on G ? H.

Theorem 2.2. If G and H are two simple connected graphs, then

max
{
D(G2H),D(G),D(H)

}
≤ D(G?H) ≤ min

{
D(G)|V (H)|, |V (G)|D(H)

}
.

Proof. We first show that max{D(G),D(H)}≤ D(G?H). By contradiction,
we assume that D(G ? H) < max{D(G),D(H)}. Without loss of generality we
suppose that max{D(G),D(H)} = D(G). Let C be a (D(G?H))-distinguishing
labeling of G ? H. Then the set of vertices {(g,h∗) : g ∈ V (G)}, where
h∗ ∈ V (H) have been labeled with less than D(G) labels. Hence we can define
the labeling C′ with C′(g) := C(g,h∗) for all g ∈ V (G). Since D(G ? H) <
D(G), so C′ is not a distinguishing labeling of G, and so there exists a nonidentity
automorphism α of G preserving the labeling C′. Thus there exists a nonidentity
automorphism λ of G?H with λ(g,h) := (α(g),h) for g ∈ V (G) and h ∈ V (H),
such that λ preserves the distinguishing labeling C, which is a contradiction. Now
we show that D(G2H) ≤ D(G ? H), and so we prove the left inequality. By
Theorems 1.1 and 2.1, we can obtain that Aut(G2H) ⊆ Aut(G ? H), and since
V (G2H) = V (G ? H), we have D(G2H) ≤ D(G ? H).

Now we show that D(G ? H) ≤ min{D(G)|V (H)|, |V (G)|D(H)}. For
this purpose, we define two distinguishing labelings of G ? H with D(G)|V (H)|
and |V (G)|D(H) labels, respectively. Let C be a D(G)-distinguishing label-
ing of G and C′ be a D(H)-distinguishing labeling of H. We suppose that
V (G) = {g1, . . . ,gn} and V (H) = {h1, . . . ,hm}, and define the two following
distinguishing labelings L1 and L2 of G?H with D(G)|V (H)| and |V (G)|D(H)
labels.

L1(gj,hi) := (i−1)D(G) + C(gj),
L2(gj,hi) := (j −1)D(H) + C′(hi).

82



The distinguishing number and the distinguishing index of co-normal product of
two graphs

We only prove that the labeling L1 is a distinguishing labeling, and by a similar
argument, it can be concluded that L2 is a distinguishing labeling of G ? H. If f
is an automorphism of G ? H preserving the labeling L1, then f maps the set
Hi := {(gj,hi) : gj ∈ V (G)} to itself, setwise, for all i = 1, . . . ,m. Since the
restriction of f to Hi can be considered as an automorphism of G preserving the
distinguishing labeling C, so for every 1 ≤ i ≤ m, the restriction of f to Hi is the
identity automorphism. Hence f is the identity automorphism of G ? H. 2

The bounds of Theorem 2.2 are sharp. For the right inequality it is sufficient to
consider the complete graphs as the graphs G and H. In fact, if G = Kn and H =
Km, then G ? H = Knm. For the left inequality we consider the non isomorphic
rigid graphs as the graphs G and H. Then by Theorem 1.4, we conclude that
G ? H and G2H are a rigid graph and hence max

{
D(G2H),D(G),D(H)

}
=

D(G ? H).

With respect to Theorems 1.1 and 1.2, we have that the automorphism group
of a co-normal product of connected non isomorphic, non rigid graphs with no
false twin and no dominating vertex, is the same as automorphism group of the
Cartesian product of them, so the following theorem follows immediately:

Theorem 2.3. If G and H are two simple connected, non isomorphic, non rigid
graphs with no false twin and no dominating vertex, then D(G?H) = D(G2H).

Since the path graph Pn (n ≥ 4), and the cycle graph Cm (m ≥ 5) are con-
nected, graphs with no false twin and no dominating vertex, then by Theorem 2.3
we have D(Pn ? Pq) = D(Pn ? Cm) = D(Cm ? Cp) = 2 for any q,n ≥ 3, where
q 6= n and m,p ≥ 5, where m 6= p. (see [7] for the distinguishing number of
Cartesian product of these graphs).

To prove the next result, we need the following lemmas.

Lemma 2.1. [13] For any two distinct vertices (vi,uj) and (vr,us) in G ? H,
N((vi,uj)) = N((vr,us)) if and only if

(i) vi = vr in G and N(uj) = N(us) in H, or

(ii) uj = us in H and N(vi) = N(vr) in G, or

(iii) N(vi) = N(vr) in G and N(uj) = N(us).

Lemma 2.2. [13] A vertex (vi,uj) is a dominating vertex in G ? H if and only if
vi and uj are dominating vertices in G and H, respectively.

Theorem 2.4. [12] For a rigid graph G and a non rigid graph H, |Aut(G?H)| =
|Aut(H)| if and only if G has no dominating vertex and H has no false twin.

83



Saeid Alikhani, Samaneh Soltani

Now we are ready to state and prove the main result of this section.

Theorem 2.5. Let G be a connected graph with no false twin and no dominating
vertex, and ?Gk the k-th power of G with respect to the co-normal product. Then
D(?Gk) = 2 for k ≥ 3. In particular, if G is a rigid graph, then for k ≥ 2,
D(?Gk) = 2.

Proof. By Lemmas 2.1 and 2.2, we can conclude that G ? G has no false twin
and no dominating vertex. We consider the two following cases:

Case 1) Let G be a non rigid graph. If H := G ? G, then D(?G3) = 2 by
Theorem 2.3. Now by induction on k, we have the result.

Case 2) Let G be a rigid graph. In this case, |Aut(G ? G)| = 2, by Theorem
1.3, and so D(G ? G) = 2. If H := G ? G, then |Aut(G ? H)| = |Aut(H)|, by
Theorem 2.4. Hence |Aut(?G3)| = 2. By induction on k and using Theorem 2.4,
we obtain D(?Gk) = 2 for k ≥ 2, where G is a rigid graph. 2

3 Distinguishing index of co-normal product of two
graphs

In this section we investigate the distinguishing index of co-normal product of
graphs. Pilśniak in [11] showed that the distinguishing index of traceable graphs,
graphs with a Hamiltonian path, of order equal or greater than seven is at most
two.

Theorem 3.1. [11] If G is a traceable graph of order n ≥ 7, then D′(G) ≤ 2.

We say that a graph G is almost spanned by a subgraph H if G−v, the graph
obtained from G by removal of a vertex v and all edges incident to v, is spanned
by H for some v ∈ V (G). The following two observations will play a crucial role
in this section.

Lemma 3.1. [11] If a graph G is spanned or almost spanned by a subgraph H,
then D′(G) ≤ D′(H) + 1.

Lemma 3.2. Let G be a graph and H be a spanning subgraph of G. If Aut(G) is
a subgroup of Aut(H), then D′(G) ≤ D′(H).

Proof. Let to call the edges of G which are the edges of H, H-edges, and the
others non-H-edges, then since Aut(G) ⊆ Aut(H), we can conclude that each
automorphism of G maps H-edges to H-edges and non-H-edges to non-H-edges.
So assigning each distinguishing edge labeling of H to G and assigning non-H-
edges a repeated label we make a distinguishing edge labeling of G.

84



The distinguishing number and the distinguishing index of co-normal product of
two graphs

Since for two distinct simple non isomorphic, non rigid connected graphs,
with no false twin and no dominating vertex we have Aut(G?H) = Aut(G2H),
so a direct consequence of Lemmas 3.1 and 3.2 is as follows:

Theorem 3.2. (i) If G and H are two simple connected graphs, then D′(G ?
H) ≤ D′(G2H) + 1.

(ii) If G and H are two simple connected non isomorphic, non rigid graphs with
no false twin and no dominating vertex, then D′(G ? H) ≤ D′(G2H).

Theorem 3.3. Let G be a connected graph with no false twin and no dominating
vertex, and ?Gk the k-th power of G with respect to the co-normal product. Then
for k ≥ 3, D′(?Gk) = 2. In particular, if G is a rigid graph, then for k ≥ 2,
D′(?Gk) = 2.

Proof. By Lemmas 2.1 and 2.2, we can conclude that G ? G has no false twin
and no dominating vertex. We consider the two following cases:

Case 1) Let G be a non rigid graph. If H = G ? G, then D(?G3) = 2 by
Theorem 3.2(ii). Now by an induction on k, we have the result.

Case 2) Let G be a rigid graph. In this case, |Aut(G ? G)| = 2, by Theorem
1.3, and so D(G ? G) = 2. If H := G ? G, then |Aut(G ? H)| = |Aut(H)|, by
Theorem 2.4. Hence |Aut(?G3)| = 2. By an induction on k and using Theorem
2.4, we obtain D(?Gk) = 2 for k ≥ 2, where G is a rigid graph.

Theorem 3.4. Let G be a connected graph of order n ≥ 2. Then D′(G?Km) = 2
for every m ≥ 2, except D′(K2 ? K2) = 3.

Proof. Since |Aut(G ? Km)| ≥ 2, so D′(G ≥ Km) = 2. With respect to
the degree of vertices G ? Km we conclude that G ? Km is a traceable graph. We
consider the two following cases:

Case 1) Suppose that n ≥ 2. If m ≥ 3, or m = 2, and n ≥ 4, then the order of
G?Km is at least 7, and so the result follows from Theorem 3.1. If m = 2, n = 3,
then G = P3 or K3. In each case, it is easy to see that D′(G ? Km) = 2.

Case 2) Suppose that n = 2. Then G = K2, and so G ? Km = K2m. Thus
D′(G ? Km) = 2 for m ≥ 3, and D′(K2 ? K2) = D′(K4) = 3. 2

By the value of the distinguishing index of Cartesian product of paths and
cycles graphs in [3] and Theorem 3.2, we can obtain this value for the co-normal
product of them as the two following corollaries.

Corolary 3.1. (i) The co-normal product Pm?Pn of two paths of orders m ≥ 2
and n ≥ 2 has the distinguishing index equal to two, except D′(P2?P2) = 3.

(ii) The co-normal product Cm ? Cn of two cycles of orders m ≥ 3 and n ≥ 3
has the distinguishing index equal to two.

85



Saeid Alikhani, Samaneh Soltani

(iii) The co-normal product Pm ? Cn of orders m ≥ 2 and n ≥ 3 has the distin-
guishing index equal to two.

Proof.

(i) If n,m ≥ 4, then the result follows from Theorem 3.2 (ii). If n = 2 or
m = 2, then we have the result by Theorem 3.4. For the remaining cases,
with respect to the degree of vertices in Pm ? Pn, we obtain easily the dis-
tinguishing index.

(ii) If n,m ≥ 5, then the result follows from Theorem 3.2 (ii). If n = 3 or
m = 3, then we have the result by Theorem 3.4. For the remaining cases
we use of Hamiltonicity of Cm ? Cn and Theorem 3.1.

(iii) If n ≥ 5 and m ≥ 4, then the result follows from Theorem 3.2 (ii). If n = 3
or m = 2, then we have the result by Theorem 3.4. The remaining cases
are Cn ? P3 and C4 ? Pm. In the first case and with respect to the degree of
vertices in Cn ? P3, we obtain easily the distinguishing index. In the latter
case, we use of Hamiltonicity of C4 ? Pm and Theorem 3.1. 2

4 Acknowledgements
The authors would like to express their gratitude to the referee for her/his

careful reading and helpful comments.

References
[1] M.O. Albertson and K.L. Collins, Symmetry breaking in graphs, Electron. J.

Combin. 3 (1996), #R18.

[2] S. Alikhani and S. Soltani, The distinguishing number and distinguishing in-
dex of the lexicographic product of two graphs, Discuss. Math. Graph Theory
38 (2018) 853-865.

[3] A. Gorzkowska, R. Kalinowski, and M. Pilśniak, The distinguishing index of
the Cartesian product of finite graphs, Ars Math. Contem. 12 (2017), 77-87.

[4] R. Hammack, W. Imrich and S. Klavžar, Handbook of product graphs (sec-
ond edition), Taylor & Francis group 2011.

[5] W. Imrich, Automorphismen und das kartesische Produkt von Graphen,
Oesterreich. Akad. Wiss. Math.-Natur. Kl. S.-B. II 177 (1969), 203-214.

86



The distinguishing number and the distinguishing index of co-normal product of
two graphs

[6] W. Imrich, J. Jerebic and S. Klavžar, The distinguishing number of Cartesian
products of complete graphs, European J. Combin. 29 (4) (2008), 922-929.

[7] W. Imrich and S. Klavžar, Distinguishing Cartesian powers of graphs, J.
Graph Theory, 53.3 (2006), 250-260.

[8] R. Kalinowski and M. Pilśniak, Distinguishing graphs by edge colourings,
European J. Combin. 45 (2015), 124-131.

[9] D.J. Miller, The automorphism group of a product of graphs, Proc. Amer.
Math. Soc. 25 (1970), 24-28.

[10] O. Ore, Theory of Graphs, Amer. Math. Society 1962.

[11] M. Pilśniak, Improving upper bounds for the distinguishing index, Ars Math.
Contemp. 13 (2017), 259-274.

[12] S. Rehman and I. Javaid, Fixing number of co-noraml product of graphs,
arXiv:1703.00709 (2017).

[13] S. Rehman and I. Javaid, Resolving, dominating and locating dominating
sets in co-normal product of graphs, submitted.

87