ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 20 (2021) 223–231
https://doi.org/10.26493/1855-3974.2173.71a
(Also available at http://amc-journal.eu)
Nordhaus-Gaddum type inequalities
for the distinguishing index
Monika Pilśniak
AGH University, Department of Discrete Mathematics,
al. Mickiewicza 30, 30-059 Krakow, Poland
Received 6 November 2019, accepted 1 March 2021, published online 3 November 2021
Abstract
The distinguishing index of a graph G, denoted by D′(G), is the least number of colours
in an edge colouring of G not preserved by any nontrivial automorphism. This invariant
is defined for any graph without K2 as a connected component and without two isolated
vertices, and such a graph is called admissible. We prove the Nordhaus-Gaddum type
relation:
2 ≤ D′(G) +D′(G) ≤ ∆(G) + 2
for every admissible connected graph G of order |G| ≥ 7 such that G is also admissible.
Keywords: Symmetry breaking in graphs, distinguishing index, Nordhaus-Gaddum type bounds.
Math. Subj. Class. (2020): 05C15, 05C25
1 Introduction and main result
We consider finite graphs and their edge colourings, not necessarily proper. Such a colour-
ing breaks an automorphism of a graph if there exists an edge that is mapped into an edge
with a different colour by that automorphism. A colouring is called asymmetric (or dis-
tinguishing), if it breaks all non-trivial automorphisms. The minimum number of colours
in an asymmetric colouring of a graph G is called the distinguishing index of G and is
denoted by D′(G). Obviously, the distinguishing index is defined only for graphs without
K2 as a component and with at most one isolated vertex. We call such graphs admissible.
The following general upper bound for the distinguishing index of connected graphs
with respect to the maximum degree was proved by Kalinowski and Pilśniak in [8].
E-mail address: pilsniak@agh.edu.pl (Monika Pilśniak)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
224 Ars Math. Contemp. 20 (2021) 223–231
Theorem 1.1 ([8]). If G is a connected graph with at least three vertices, then
D′(G) ≤ ∆(G)
unless G is C3, C4 or C5.
This result was improved in [10], where all connected graphs with the distinguishing
index equal to the maximum degree were characterized. In particular, a tree is called sym-
metric (respectively, bisymmetric) if it contains a central vertex v0 (resp. a central edge e0),
all leaves are at the same distance from v0 (resp. e0) and all vertices that are not leaves have
the same degree.
Theorem 1.2 ([10]). Let G be a connected graph of order at least three. Then
D′(G) ≤ ∆(G)− 1
unless G is a cycle, a symmetric or a bisymmetric tree, K4 or K3,3.
In the same paper, the conjecture for 2-connected graphs was formulated, and quite
recently was confirmed in [7] in a bit stronger form, as follows.
Theorem 1.3 ([7]). If G is a connected graph with minimum degree δ(G) ≥ 2, then
D′(G) ≤
⌈√
∆(G)
⌉
+ 1.
The main goal of the paper is a proof of a Nordhaus-Gaddum type inequalities for
the distinguishing index of a graph. Our investigation was motivated by the renowned result
of Nordhaus-Gaddum [9] who determined in 1956 lower and upper bounds for the sum
of the chromatic numbers of a graph and its complement (actually, the upper bound was
first proved by Zykov [12] in 1949). Since then, Nordhaus-Gaddum type bounds were
obtained for many graph invariants. An exhaustive survey is given in [1]. In particular,
it was considered by Collins and Trenk in [3] for the distinguishing chromatic number
χD(G), which is the minimum number of colours in an asymmetric proper vertex colouring
of a graph G. The Nordhaus-Gaddum type inequalities were also investigated in [10] for
the chromatic distinguishing index χ′D(G) of a graph G defined for asymmetric proper
edge colourings. It was proved therein that if G is an admissible graph of order n ≥ 3
distinct from K1,4, then
n− 1 ≤ χ′D(G) + χ′D(G) ≤ 2(n− 1).
Both upper and lower bounds are similar to Vizing bounds proved for the chromatic index
of a graph [11] but in the proof for the chromatic distinguishing index we have to be more
careful.
It was also conjectured in [10] that
2 ≤ D′(G) +D′(G) ≤ max{∆(G),∆(G)}+ 2
if both graphs G and G are admissible and of order n ≥ 7. It was confirmed for some
classes of graphs, in particular for trees, claw-free graphs, 3-connected graphs and traceable
graphs. Here, we prove the stronger version of Nordhaus-Gaddum type inequality for
the distinguishing index.
M. Pilśniak: Nordhaus-Gaddum type inequalities for the distinguishing index 225
Theorem 1.4 (Main Theorem). If both G and G are admissible graphs of order n ≥ 7,
and G is connected, then
2 ≤ D′(G) +D′(G) ≤ ∆(G) + 2.
The lower bound by 2 is obvious. Indeed, if a graph G is asymmetric, that means it
has a trivial automorphism group, then the distinguishing index of both G and G equals 1.
Moreover, Theorem 1.4 is tight. To see this, consider a symmetric (or bisymmetric) tree
T of order n ≥ 7. Then by [5] T contains an asymmetric spanning tree if T is different
from a star, so D′(T ) = 2 by Proposition 2.2. So, it follows from Theorem 1.2 that
D′(T ) +D′(T ) = ∆(T ) + 2 for symmetric and bisymmetric trees.
It has to be noted that there exist graphs of order less than 7 violating the right inequal-
ity in Theorem 1.4. For example, D′(K3,3) = 3, D′(K3,3) = 4, whence D′(K3,3) +
D′(K3,3) = ∆(K3,3) + 4. Also, D′(C5) + D′(C5) = ∆(C5) + 4, and D′(K1,i) +
D′(K1,i) = ∆(K1,i) + 3 for i = 3, 4, 5.
In Section 2 we recall some results useful in the proof of Theorem 1.4, which is given
in Section 3.
2 Known bounds for D′
Let us recall some useful results, before we start to prove the Main Theorem. A graph
that contains a Hamiltonian path, i.e. a path that visits each vertex of the graph, is called
traceable. Following [2], we define the k-th Bondy-Chvátal closure clk(G) of a graph G
as the graph obtained from G by recursively joining pairs of non-adjacent vertices with
degree-sum at least k. By the well-known theorem of Bondy and Chvátal [2], a graph G of
order n is traceable whenever cln−1(G) is traceable.
We begin with the distinguishing index of complete graphs and of traceable graphs.
Proposition 2.1 ([8]).
D′(Kn) =
{
2, if n ≥ 6,
3, if n = 3, 4, 5.
The following simple observation is very useful in some proofs. A subgraph H of a
graph G is called almost spanning if H is a spanning subgraph of a graph G− v for some
v ∈ V (G).
Proposition 2.2 ([10]). If H is a spanning or almost spanning subgraph with at least three
vertices of a graph G, then D′(G) ≤ D′(H) + 1.
In particular, the spanning path in a traceable graph needs two colours to break its non-
trivial automorphism, so a traceable graph has the distinguishing index at most 3. Actually
we have a stronger result.
Theorem 2.3 ([10]). Let G be a traceable graph of order at least 3. If G has at least 7
vertices, then D′(G) ≤ 2. Moreover, if G is of order at most 6, then D′(G) ≤ 3.
The distinguishing index of complete bipartite graphs was determined independently by
Fisher and Isaak [4] and by Imrich, Jerebic and Klavžar [6]. Actually, they formulated their
result for the distinguishing number D(Kp □Kq) of the Cartesian product of complete
graphs, but D′(Kp,q) = D(Kp □Kq).
226 Ars Math. Contemp. 20 (2021) 223–231
Theorem 2.4 ([4, 6]). Let p, q, d be integers such that d ≥ 2 and (d− 1)p < q ≤ dp. Then
D′(Kp,q) =
{
d, if q ≤ dp − ⌈logd p⌉ − 1,
d+ 1, if q ≥ dp − ⌈logd p⌉+ 1.
If q = dp − ⌈logd p⌉, then the distinguishing index D′(Kp,q) is either d or d + 1 and can
be computed recursively in O(log∗(q)) time.
In the rest of the paper, we make use of the following immediate corollary.
Corollary 2.5. If p ≤ q, then D′(Kp,q) ≤ ⌈ p
√
q⌉+ 1.
The following simple observation is used later in this section.
Proposition 2.6. If H is an admissible disconnected graph of order at least 7, then
D′(H) ≤ |H| − 2.
Proof. Theorem 1.2 implies that the only connected graph H with D′(H) ≥ |H| − 1 is
K3,K4, C4 or a star K1,n−1 for n ≥ 3. If all components H1, . . . ,Hs of H are pairwise
non-isomorphic, then D′(H) = max{D′(Hi) : i = 1, . . . , s}, so D′(H) ≤ |H| − 2. If H
contains t ≥ 2 copies of a graph H1 as its components, so |H| ≥ t|H1|, then we colour
one of them distinguishingly and use one extra colour for each other copy. Hence,
D′(tH1) ≤ D′(H1) + t− 1 ≤ |H1|+ t− 1 ≤
|H|
t
+ t− 1 ≤ |H| − 2.
We easily extend a result of [10] for trees to forests. First, recall a result of Hedetniemi
et al. [5] on packing two trees into Kn.
Theorem 2.7 ([5]). A complete graph Kn contains edge disjoint copies of any two trees of
order n distinct from a star K1,n−1.
Proposition 2.8. Let G be an admissible graph of order n such that G is an admissible
forest. Then D′(G) ≤ 2 if n ≥ 7, and D′(G) ≤ 3 otherwise.
Proof. The case when G is a tree was proved in [10]. Otherwise, it easily follows from
Theorem 2.7 that G contains a Hamiltonian path Pn. Indeed, we can consider a tree F ′
spanned by G, and every tree distinct from a star is included in a subgraph F ′ of G. Thus
D′(G) ≤ 2 if n ≥ 7, and D′(G) ≤ 3 if 3 ≤ n ≤ 6 by Theorem 2.3.
Additionally, let us note the following observation for small graphs. Denote by W1 and
W2 the two graphs from Figure 1 called windmills.
W1
b b
bb b
b b
W2
b
b
bb b
b b
Figure 1: Two windmills.
M. Pilśniak: Nordhaus-Gaddum type inequalities for the distinguishing index 227
Proposition 2.9. If G is a connected graph of order at most 7 different from windmills W1
and W2, and from a star K1,n for n = 4, 5, 6, then D′(G) ≤ 3.
Proof. Observe that if ∆(G) ≤ 4, then the claim holds by Theorem 1.2. So let ∆(G) ≥ 5.
First assume that G does not have pendant edges. If the longest cycle in G is of order at
least 6, then G is traceable and D′(G) ≤ 3 by Theorem 2.3. If the longest cycle C in G
is of order 5, then we colour the edges of this cycle with 0, 1, 0, 2, 0 (in this order) and all
chords with 1. Thus, each vertex of C has an incident edge coloured with 0. If there exists
a vertex of G with noncoloured incident edges, then all of them we colour with 2 and all
the remaining edges with 1. It is an asymmetric colouring of G, because outside the initial
cycle C we create a monochromatic vertex with colour 2 and a monochromatic vertex with
colour 1 or a bichromatic one with colours 1 and 2.
If the longest cycle in G is of order 4, then a 2-connected G is isomorphic to K2,r
or K2,r + e with r ≤ 5 where e is an edge between two vertices of maximum degree.
Three colour suffice for an asymmetric colouring of r paths of length two between the two
vertices of maximum degree. If such a 2-connected graph is joined with a triangle (in a cut
vertex), then we can colour every edge of the triangle with a different colour. If two cycle
of length 4 (with chords) meet in only one vertex, then an asymmetric colouring of one of
them uses colour 1 twice, while the other one uses 2 twice (apart from one edge coloured
with 0).
If the longest cycle is a triangle C3, then G has a cut vertex v where three cycles meet.
Then a pair of edges including v in every triangle is coloured with 1 and 2, while every
remaining edge obtains a distinct colour 1, 2 or 3.
Now assume that there exists a leaf v in G. First suppose there exists an induced
subgraph B of G with minimal degree at least 2. Then we can colour it with three colours
as above. So we have to distinguish now only pendant trees (in particular paths and edges)
with a common vertex just fixed in B. It is always possible to do this with three colours if
|G| ≤ 7 unless B has a pendant star K1,4. Then we obtain an exceptional graph W1.
Finally, let G be a tree of order at most 7 different from a star K1,n with n = 3, . . . , 6.
Then D′(G) ≤ ∆(G) − 1 by Theorem 1.2. Clearly, D′(G) ≤ 3 unless G = W2, which
needs four colours like W1.
3 Proof of the Main Theorem
Proof of Theorem 1.4. Let G be a connected graph of order n ≥ 7 such that both G and its
complement G are admissible. Denote ∆ = ∆(G). Clearly, ∆ ≥ ∆(G) + 1 whenever G
is disconnected. Next, if ∆ ≤ n−12 , then
δ(G) = n− 1−∆ ≥ n− 1
2
,
and G is connected. Otherwise, n−12 ≥ ∆ ≥ ∆(G) + 1 ≥
n−1
2 + 1. Hence, G satisfies
the well-known Dirac’s condition for traceability, so G is traceable. Hence, D′(G) +
D′(G) ≤ ∆+ 2 by Theorem 1.1 and Theorem 2.3.
Assume then that ∆ ≥ ⌈n2 ⌉. Analogously, we can assume that ∆(G) ≥ ⌈
n
2 ⌉. Indeed,
our theorem holds if ∆(G) ≤ n−12 . Then D
′(G) ≤ 2 and D′(G) ≤ ∆(G) ≤ n−12 ≤ ∆ if
G is connected, or D′(G) ≤ ⌈n2 ⌉ ≤ ∆ if G is disconnected, by the following reasons.
Theorem 1.1 implies that the only connected graphs H with D′(H) > ∆(H) are
C3, C4 and C5. If all components H1, . . . ,Hs of G are pairwise non-isomorphic, then
228 Ars Math. Contemp. 20 (2021) 223–231
D′(G) = max{D′(Hi) : i = 1, . . . , s} ≤ max{3,∆(Hi)}, so D′(G) ≤ n2 . If G contains
ti ≥ 2 copies of a graph Hi as its components, then let t = max{ti : i = 1, . . . , s} and let
H = Hl where D′(Hl) = max{D′(Hi) : i = 1, . . . , s}, and we colour one copy of Hl
distinguishingly and use one extra colour for each other copy. So, for H different from C3,
C4 and C5 we have
D′(G) ≤ D′(tHl) ≤ D′(Hl) + t− 1 ≤ ∆(Hl) + t− 1 ≤
|G|
t
+ t− 2 ≤ n
2
,
and for i ∈ {3, 4, 5} we obtain D′(tCi) ≤ t+ 2 ≤ ⌈ ti2 ⌉.
We distinguish two cases.
Case A: Both G and G are connected graphs without pendant edges.
Then D′(G) ≤ ⌈
√
∆⌉+1 and D′(G) ≤ ⌈
√
∆(G)⌉+1. Hence, the inequality D′(G)+
D′(G) ≤ ∆+ 2 is weaker than
∆−
⌈√
∆
⌉
≥
⌈√
∆(G)
⌉
. (3.1)
First assume that ∆ ≥ ∆(G). It is easy to see that the inequality (3.1) is satisfied unless
∆ = ∆(G) = 5. In the latter case 8 ≤ n ≤ 10 and δ(G) = δ(G) = n − 6. We want to
show that either G or its complement G is traceable.
We say that a sequence (ai) is minorized by a sequence (bi) if bi ≤ ai for any i.
If n = 8, then the degree sequence, ordered non-increasingly, of G (or G) is minorized
by (5, 5, 4, 4, 2, 2, 2, 2) or by (5, 4, 4, 4, 3, 2, 2, 2). Indeed, we know by assumptions that
b1 = 5, b8 = 2, two terms of bi have to be odd since the sum of degrees is even in every
graph, and the sum of the fourth term of the sequence of G and the fifth term of the sequence
of G equals n − 1 = 7, so one of them cannot be smaller than ⌈n−12 ⌉ = 4. Now, by
definition of the (n − 1)-th Bondy-Chvátal closure cln−1(G), a vertex of degree five in G
has degree n − 1 = 7 in cl7(G), so we have to add two new edges incident to it. Observe
that adding new edges yields another vertex that has degree n − 1 in cl7(G), and this is
the case at each step of creating cl7(G). Finally, cl7(G) = K8. Hence, G is traceable, by
the Bondy-Chvátal theorem [2].
Similarly, if n = 9, we may assume that the degree sequence of G is minorized
by (5, 4, 4, 4, 4, 4, 3, 3, 3) or by (5, 5, 4, 4, 4, 3, 3, 3, 3), and it is not difficult to see that
cl8(G) = K9. For n = 10, the degree sequence of G is minorized by (5, 5, 4, . . . , 4) and
here it is clear that cl9(G) = K10. For brevity, the details are left to the reader.
Now assume that ∆(G) > ∆. Then it is easily seen that the inequality (3.1) holds for
any ∆, ∆(G) and n unless either n = 8,∆ = 4,∆(G) = 5, or n = 9,∆ = 5,∆(G) = 6,
or n = 10,∆ = 5,∆(G) ∈ {6, 7}, since ⌈n2 ⌉−⌈
√
⌈n2 ⌉⌉ ≥ ⌈
√
n− 3⌉. The same argument
as above confirms that G is traceable.
Case B: A graph G is disconnected or δ(G) = 1.
If G is a forest, then the conclusion follows from Proposition 2.8. Hence, assume that
G contains a 2-connected block. We now consider decompositions of G into two subgraphs
F1, F2 such that E(F1) ∪ E(F2) = E(G) and the vertex sets V (F1), V (F2) share at most
one vertex which is a cut-vertex of G. Denote p = |F1|−1, q = |F2|−1 if F1 and F2 share
a common vertex, and p = |F1|, q = |F2| if F1 and F2 are disjoint. Assume that p ≤ q
and the difference q − p is smallest possible. Observe that ∆(G) ≥ q and G is spanned or
almost spanned by a complete bipartite graph Kp,q .
M. Pilśniak: Nordhaus-Gaddum type inequalities for the distinguishing index 229
First, suppose that q ≤ 2p − p. Then D′(G) ≤ 2, since G is (almost) spanned by
an asymmetric spanning subgraph of Kp,q for p + q ≥ 7 by Proposition 3.10 in [10] (see
also [6]).
If G is connected, then ∆ = ∆(G) = n − 2 since δ(G) = 1 by the assumption of
Case B. Moreover, D′(G) ≤ n− 2 by Theorem 1.1 as ∆(G) ≤ n− 2. Hence
D′(G) +D′(G) ≤ 2 + n− 2 = ∆+ 2.
If G is disconnected, then either δ(G) = 1 or δ(G) ≥ 2. If δ(G) = 1, then D′(G) ≤
n− 2 by Proposition 2.6 and D′(G) +D′(G) ≤ 2 + n− 2 = ∆+ 2. Now, let δ(G) ≥ 2,
and assume (in the worst case) that G contains s components isomorphic to a connected
graph H . Recall that ∆(G) ≥ n2 , as we assumed at the beginning of the proof. So,
3 ≤ |H| < n2s . If we use a distinct additional colour for every component H , then D
′(G) ≤
⌈
√
∆(G)⌉+ s ≤ ⌈
√
n− 2⌉+ s, by Theorem 1.3. So, we would like to show that⌈√
n− 2
⌉
+ s+ 2 ≤ n− |H|+ 2, (3.2)
since ∆(G) ≥ n− |H|. To confirm the inequality (3.2), we estimate⌈√
n− 2
⌉
+ s ≤
⌈√
n− 2
⌉
+
n
6
≤ n− n
4
≤ n− |H|.
It is easy to verify that the second inequality is always true. The last inequality is obvious
if s is at least 2. If s = 1 we do not need to distinguishing connected component one from
another, hence we use the same colours in every component and D′(G) ≤ ⌈
√
∆(G)⌉+1 ≤
∆. So, this subcase is completed.
Now, assume that q ≥ 2p − p+ 1. Then D′(G) ≤ p√q + 2 for p ≥ 2 by Corollary 2.5
and Proposition 2.2. In this case the graph G can be obtained from a 2-connected graph B
by attaching a number of independent pendant subgraphs (of order at most p) to it or there
is a component of order p and a 2-connected component B of order q. Hence, ∆(B) ≤ q
and D′(G) ≤ ⌈√q⌉+ 1, by Theorem 1.3 for the block B, and by the observation that then
every subgraph attached to B has one vertex fixed and the order at most p ≤ √q + 2. We
obtain D′(G) + D′(G) ≤ ⌈ p√q⌉ + 2 + ⌈√q⌉ + 1. Recall that ∆ ≥ q, so it is enough to
check whether
⌈ p√q⌉+ ⌈√q⌉+ 3 ≤ q + 2.
Consequently, we obtain the inequality
q − ⌈ p√q⌉ − ⌈√q⌉ − 1 ≥ 0. (3.3)
For p = 3, we have q ≥ 23 − 3 + 1 = 6. For q = 6, p = 3 we have D′(G) ≤ 4
by Proposition 2.2, and D′(G) ≤ 3 by Proposition 2.9 for F2. Observe now that the
inequality (3.3) is satisfied, because it holds for q = 7, and q − ⌈ 3√q⌉ − ⌈√q⌉ − 1 is an
increasing function of q. The inequality (3.3) also holds for larger values of p since its
left-hand side is non-decreasing with respect to p.
If p = 2, then inequality (3.3) is satisfied for q ≥ 7. For q = 5 or q = 6, G is
(almost) spanned by K2,5 or K2,6, so D′(G) ≤ 4 by Proposition 2.2, and D′(G) ≤ 3 by
Proposition 2.9 for F2. For q = 4 we have n = 7 and our theorem is true by Proposition 2.9.
Now let p = 1. If G is disconnected, then G contains a 2-connected block B of order
n − 1 and an isolated vertex v. Hence, ∆ = n − 1, of course. Then D′(G) ≤ D′(B) ≤
230 Ars Math. Contemp. 20 (2021) 223–231
⌈
√
∆(G)⌉ + 1. Moreover, D′(G) ≤ ⌈
√
∆⌉ + 1 whenever δ(G) ≥ 2, by Theorem 1.3.
Hence,
D′(G) +D′(G) ≤ 2
⌈√
∆
⌉
+ 2,
and 2⌈
√
∆⌉+ 2 ≤ ∆+ 2 for ∆ ≥ 6, since ∆ = n− 1 ≥ 6.
If the graph G is connected, then G can be obtained from a 2-connected block B by
attaching a number (maybe zero) of independent pendant edges to it. It is enough to break
all nontrivial automorphisms of B. Then D′(G) ≤ D′(B) ≤ ⌈
√
∆(G)⌉ + 1. Moreover,
∆ = n−2 and D′(G) ≤ ⌈
√
∆⌉+1 whenever δ(G) ≥ 2, by Theorem 1.3. Then 2⌈
√
∆⌉+
2 ≤ ∆+2 for ∆ ≥ 6, unless ∆ = 5. But in the latter case n = 7 and D′(G)+D′(G) ≤ 6
by Proposition 2.9.
Finally, assume that p = 1 and δ(G) = 1. Then we consider decompositions of G into
two subgraphs F ′1, F
′
2 such that E(F
′
1)∪E(F ′2) = E(G) and the vertex sets V (F ′1), V (F ′2)
share one vertex which is a cut-vertex of G. Denote p′ = |F ′1| − 1, q′ = |F ′2| − 1. Assume
that p′ ≤ q′ and the difference q′ − p′ is smallest possible. Recall that ∆(G) = n− 2 and
G is spanned or almost spanned by a complete bipartite graph Kp′,q′ .
If q′ ≤ 2p′ − p′, then D′(G) ≤ 2 like above (for p′ + q′ ≥ 7), and D′(G) ≤ ∆ by
Theorem 1.1. So, we are done. If q′ ≥ 2p′ − p′ + 1, then D′(G) ≤ p′
√
q′ + 2 for p′ ≥ 2,
and we obtain
D′(G) +D′(G) ≤
⌈√
q′
⌉
+
⌈
p′
√
q′
⌉
+ 3 ≤ p′ + q′ + 1,
since ∆ ≥ n − 2 = p′ + q′ − 1. For p′ = 2, we have q′ ≥ 22 − 2 + 1 = 3, and
the inequality 2⌈
√
q′⌉ ≤ q′ is satisfied since n ≥ 7. Hence q′ ≥ 4. The inequality
p′ + q′ − ⌈
√
q′⌉ − ⌈ p′
√
q′⌉ − 2 ≥ 0 also holds for larger values of p′ since its left-hand side
is non-decreasing with respect to p′.
Let p′ = 1. Then there exists a 2-connected block B′ in G with a number of indepen-
dent pendant edges attached to it (at least one). Hence D′(G) ≤ D′(B′) ≤ ⌈
√
∆⌉ + 1.
Recall that also D′(G) ≤ ⌈
√
∆(G)⌉+ 1 ≤ ⌈
√
∆⌉+ 1, since ∆ = ∆(G) = n− 2. So we
verify the following inequality
2
⌈√
∆
⌉
+ 2 ≤ ∆+ 2
for ∆ ∈ {n − 2, n − 1}, which is true for n ≥ 7 unless ∆ = 5. But then n = 7 and
D′(G) +D′(G) ≤ 6 once more by Proposition 2.9.
ORCID iD
Monika Pilśniak https://orcid.org/0000-0002-3734-7230
References
[1] M. Aouchiche and P. Hansen, A survey of Nordhaus-Gaddum type relations, Discrete Appl.
Math. 161 (2013), 466–546, doi:10.1016/j.dam.2011.12.018.
[2] J. A. Bondy and V. Chvátal, A method in graph theory, Discrete Math. 15 (1976), 111–135,
doi:10.1016/0012-365x(76)90078-9.
[3] K. L. Collins and A. N. Trenk, Nordhaus-Gaddum theorem for the distinguishing chromatic
number, Electron. J. Combin. 20 (2013), #P46 (18 pages), doi:10.37236/2117.
M. Pilśniak: Nordhaus-Gaddum type inequalities for the distinguishing index 231
[4] M. J. Fisher and G. Isaak, Distinguishing colorings of Cartesian products of complete graphs,
Discrete Math. 308 (2008), 2240–2246, doi:10.1016/j.disc.2007.04.070.
[5] S. M. Hedetniemi, S. T. Hedetniemi and P. J. Slater, A note on packing two trees into KN , Ars
Combin. 11 (1981), 149–153.
[6] W. Imrich, J. Jerebic and S. Klavžar, The distinguishing number of Cartesian products of com-
plete graphs, European J. Combin. 29 (2008), 922–929, doi:10.1016/j.ejc.2007.11.018.
[7] W. Imrich, R. Kalinowski, M. Pilśniak and M. Woźniak, The distinguishing index of con-
nected graphs without pendant edges, Ars Math. Contemp. 18 (2020), 117–126, doi:10.26493/
1855-3974.1852.4f7.
[8] R. Kalinowski and M. Pilśniak, Distinguishing graphs by edge-colourings, European J. Com-
bin. 45 (2015), 124–131, doi:10.1016/j.ejc.2014.11.003.
[9] E. A. Nordhaus and J. W. Gaddum, On complementary graphs, Amer. Math. Monthly 63 (1956),
175–177, doi:10.2307/2306658.
[10] M. Pilśniak, Improving upper bounds for the distinguishing index, Ars Math. Contemp. 13
(2017), 259–274, doi:10.26493/1855-3974.981.ff0.
[11] V. G. Vizing, The chromatic class of multigraphs, Kibernetika (Kiev) 1 (1965), 29–39.
[12] A. A. Zykov, On some properties of linear complexes, Mat. Sb. (N.S.) 24 (1949), 163–188,
http://mi.mathnet.ru/eng/msb5974.