Neighbor Sum Distinguishing Index of Graphs with Maximum Average Degree ()
1. Introduction
All graphs mentioned in this paper are undirected, finite and simple. For a graph G, we denote its vertex set, edge set, maximum degree, minimum degree by
,
,
,
, respectively. Let
be the set of neighbors of the vertex v in G, and
be the degree of v in G. The
average degree of a graph G is defined as
. The maximum average degree
of G is the maximum of the average degrees of its subgraphs.
A proper k-edge coloring of a graph
is an assignment
such that
for any two adjacent edges
and
. Let c be a proper k-edge coloring of G. We use
to denote the sum of colors of the edges incident to v. If
for each edge
, then c is called as a neighbor sum distinguishing k-edge coloring or an nsd-k-coloring of G for short. The neighbor sum distinguishing index of a graph G is the least integer k such that G has an nsd-k-coloring, denoted by
. By
, we denote the set of colors taken on the edges incident to v, i.e.
. The proper k-edge coloring c is a neighbor set distinguishing k-edge coloring, if
for each edge
. Let
be the smallest value k such that G has a neighbor set distinguishing k-edge coloring. It is easy to observe that G has a neighbor sum(or set) distinguishing edge coloring if and only if G does not contain isolated edges. A graph with no isolated edges is called as a normal graph. Then
for any normal graph by definition.
In 2002, Zhang et al. [1] introduced the concept of the neighbor set distinguishing edge coloring and posed the following conjecture.
Conjecture 1.1 ( [1] ) If G is a connected normal graph with at least 6 vertices, then
.
Hatami [2] proved
by probabilistic method for normal graph G with
. Akbari et al. [3] showed that
for any normal graph. Wang et al. [4] improved this bound to that
for any normal graph.
The neighbor sum distinguishing edge coloring was introduced by Flandrin et al. [5]. They determined the neighbor sum distinguishing index of graph classes including paths, trees, cycles, complete graphs and complete bipartite graphs, and posed the following conjecture.
Conjecture 1.2. ( [5] ) If G is a connected normal graph with at least 3 vertices and
, then
.
Flandrin et al. [5] proved that
for each connected normal graph G with maximum degree
. Wang and Yan [6] improved this bound to
. Bonamy and Przybylo [7] showed that
for planar graph with
. Dong et al. [8] studied the connections between neighbor sum distinguishing index and maximum average degree, and proved that if G is a normal graph with
and
, then
. Later, Gao et al. [9] showed that if G is a normal graph with
and
, then
. Hocquard and Przybylo [10] proved that
for any normal graph G with
and
. Wang et al. [11] proved that if G is a normal graph with
and
, then
. Recently, Wang et al. [12] proved that if G is a normal graph with
and
, then
.
In this paper, we improve the result given by Wang et al. [11] and obtain the following result:
Theorem 1.1. Let G be a normal graph. If
, then
.
Corollary 1.2. Let G be a normal graph. If
and
, then
.
2. Preliminaries
To prove our main result, we need to introduce some notations. A vertex v is called a k-vertex (a
-vertex, or a
-vertex, respectively) if
(
, or
, respectively). A vertex v is called a leaf if
.
At first, we introduce several lemmas.
Lemma 2.1. ( [11] ) Suppose that k and n are positive integers with
,
is a set of integers with
,
. Let
, then
.
Lemma 2.2. ( [13] ) Let F be an arbitrary field, and let
be a polynomial in
. Suppose the degree
of P equals
, where each
is a non-negative integer, and suppose the coefficient of
in P is non-zero. Then if
are subsets of F with
, there are
so that
.
Lemma 2.3. ( [14] ) Let
be a polynomial in n variables,where
.Let
denote the coefficient of
in P,then
3. Proof of Theorem 1.1
3.1. Unavoidable Configuration
In this paper, we will prove Theorem 1.1 by contradiction. Let
. Let G be a counterexample of theorem 1.1 such that
is the smallest. Obviously, G is connected. Let H be a normal subgraph of G. By the minimality of G, H has an nsd-K-coloring c using the color set
.
Remark 1. Let
. Suppose that u is adjacent to a 2-vertex v with
and
. If
admits an nsd-K-coloring c such that
, then there are at least
colors available for vw. Hence we can get an nsd-K-coloring of G. Hence, in the following discussion, we will omit the proof of recoloring or coloring of vw, and just show that
has an nsd-K-coloring c with
.
Let H be the graph which is obtained by removing all the leaves of G. Let
(
,
) be the number of neighbors of v with degree k (at most k, at least k) in H.
Claim 3.1. The graph H has the following properties:
(1)
.
(2) If
, then
.
(3) If
is a path in H such that
,
, then
.
Proof: (1) This statement follows from [8].
(2) Assume to the contrary that
. Let
. Then u in G is adjacent to d 2+-vertices
and l leaves
.
Suppose that
. Let
. Then
by the minimality of G. The colors in
are forbidden for
. So we have at least
available colors for
. Therefore, we can get an nsd-K-coloring of G, a contradiction.
Suppose that
. Let
and
denote the feasible color set which
can use for each
. Then
colors available for
. By Lemma 2.1,
. Let
. Note that
. If
, then
. If
, then
and
. Thus, we can show that
. Hence we can get an nsd-K-coloring of G, a contradiction.
(3) According to Claim 3.1 (2), we have
and
. Assume to the contrary that
, this means that there exist at least one leave
adjacent to u in G. Let
. Then
has an nsd-K-coloring c by the minimality of G. If
, we can get an nsd-K-coloring of G by Remark 1, a contradiction. If
, then we exchange the colors of
and
, and get an nsd-K-coloring of G by Remark 1, a contradiction.
A 2-vertex is called bad if it is adjacent to a 2-vertex; weak if it is adjacent to a 3-vertex or a 4-vertex; good if it is adjacent to two 5+-vertices; deficient if it is bad or weak. Let
(
,
) be the number of bad 2-vertices (deficient vertices, good 2-vertices) adjacent to u in H.
Claim 3.2. Suppose that u is a weak 2-vertex in H. Let
, where
or 4.
(1) If
, then
.
(2) If
, then
.
Proof: (1) By Claim 3.1 (2),
and
. Let
. Assume to the contrary that
. According to Claim 3.1 (2),
. Let
. Then
has an nsd-K-coloring by the minimality of G. It is easy to see that there are at least
available colors for
. So we can extend the coloring to G by Remark 1, a contradiction.
(2) By Claim 3.1 (2),
and
. Let
. Assume to the contrary that
. By Claim 3.1 (2),
. Let
. Then
has an nsd-K-coloring by the minimality of G. There are at least
available colors for
. So we can obtain an nsd-K-coloring of G by Remark 1, a contradiction.
If
is a path of H such that
and
, then u is called the source vertex of y, y is called sink vertex of u. We use
to denote the number of sink vertices of u. By Claim 3.2 (1), we know that
.
Claim 3.3 Let
with
. Let
be the neighbors of u in H.
(1) If
, then
.
(2) If
, then
.
(3) If
, then
.
(4) If
, then
.
(4.1) If
, then
.
(4.2) If
, then
.
(4.3) If
and
, then
.
(5) If
, then
.
(5.1) If
and
, then
.
(5.2) If
, then
.
Proof: (1) Assume to the contrary that u is adjacent to two 4--vertices
and
. By Claim 3.1 (2),
and
for
. Suppose that
(If
, we can prove it similarly). Let
. Then
has an nsd-K-coloring c by the minimality of G. It is easy to show that the colors in
are forbidden for
. So we have at least
available colors for
. Then we can get an nsd-K-coloring of G by Remark 1, a contradiction.
(2) Assume to the contrary that u is adjacent to two 3--vertices
and
. By Claim 3.1 (2),
and
for
. Let
. Then
has an nsd-K-coloring c by the minimality of G. The colors in
are forbidden for
. So we have at least
available colors for
. Next, there are at least
colors available for
. Hence we have
, a contradiction.
(3) Assume to the contrary that u is adjacent to two bad 2-vertices
and
. By Claim 3.1 (2), we have
for
.
Case 1:
.
Let
. The colors in
are forbidden for
. So there are at least
available colors for
. Hence, we can extend this coloring to G, a contradiction.
Case 2:
.
Let
for
. By Claim 3.1 (2),
for
. By Claim 3.2 (1),
and
. Let
for
.
Case 2.1:
.
Let
. Then
has an nsd-K-coloring c by the minimality of G. Note that
and
. If
(similarly for
), then we switch the colors of
and
. It is worth noting that
and
for this new nsd-K-coloring
of
. The colors in
are forbidden for
. So we have at least
available colors for
. Similarly, there are at least 5 colors available for
. Hence we have
, a contradiction. If
and
, then
(
). Now we can extend this coloring to G with the similar discussion as above, a contradiction.
Case 2.2:
.
Let
. Now we will show that
. In fact, let
be the subgraph of
. If
, then
and
. So suppose that
. If at most one of
and
belongs to
, say
if it exists, then
, is the subgraph of G. Note that
. Therefore,
. If
and
, then
is the subgraph of G. Note that
. Therefore,
. Thus, we obtain that
is a graph with
and
. Then
has an nsd-K-coloring c by the minimality of G. Note that
by
. Then we can achieve an nsd-K-coloring of G with the similar discussion as Case 2.1.
(4) Assume to the contrary that u in H is adjacent to three 2-vertices
and
. By Claim 3.1 (2), it holds that
for
. Let
for each
. Assume that u in G is adjacent to l leaves
with
.
Case 1:
.
Then
. Let
. Then
has an nsd-K-coloring by the minimality of G. It is easy to see that there are at least
colors available for
(
). By Lemma 2.1,
. So we can color
,
and
properly such that
for each
, a contradiction.
Case 2:
.
Let
. Then
has an nsd-K-coloring by the minimality of G. It is evident that there are at least
colors available for
(
) and at least
colors available for
. By Lemma 2.1,
. So we can color
,
,
and
properly and obtain an nsd-K-coloring of G, which is a contradiction.
Case 3:
.
Let
. Then
has an nsd-K-coloring by the minimality of G. We use colors
to color
. Let
and
devote the available color set for
(
) and
, respectively. Now we consider the following polynomial:
Let
Suppose that
. Let
. Notice that
and
. By computations, we obtain that
. According to Lemma 2.2, we can choose
(
) such that
. That is, we can get an nsd-K-coloring of G, a contradiction.
Suppose that
. Let
. It is evident that for each
, we have
and
. By computations, we obtain that
. According to Lemma 2.2, we can choose
(
) such that
. That is, we can get an nsd-K-coloring of G, a contradiction.
(4.1) Assume to the contrary that u in H is adjacent to one deficient vertex
and has one sink vertex x. Let
. Then by the definition of sink vertex, we have
,
. By Claim 3.1, it holds that
,
,
and
. Suppose that
. Let
. Then
has an nsd-K-coloring by the minimality of G. We erase the colors on edges
and
. There are at least
available colors for
. Thus, we can color properly the edge
such that
for
. Then we can get an nsd-K-coloring of G by Remark 1, a contradiction.
(4.2) Assume to the contrary that u in H is adjacent to two deficient vertices
and
. By Claim 3.1, it holds that
,
and
(
). Suppose that
for each
. Let
. Then
has an nsd-K-coloring by the minimality of G. We erase the colors on edges
for
. There are at least
available colors for
. So we can color
. Next, we have at least
colors available for
. Thus, we can color properly the edge
such that
for
. Then we can get an nsd-K-coloring of G by Remark 1, a contradiction.
(4.3) Assume that u in H is adjacent to one deficient vertex
, one good 2-vertex
and one 3-vertex
. By Claim 3.1, it holds that
,
(
) and
. Suppose that
for each
. Let
. Then
has an nsd-K-coloring by the minimality of G. Firstly, we erase the colors on edge
. Then there are at least
available colors for
and at least
available colors for
, and at least
colors available for
. By Lemma 2.1,
. So we can color
,
and
properly and obtain an nsd-K-coloring of G by Remark 1, which is a contradiction.
(5) Assume that u of H is adjacent to two deficient vertices
and
. By Claim 3.1, it holds that
,
and
for
. Suppose that
for
. Let
. Then
has an nsd-K-coloring by the minimality of G. We erase the colors on edges
(
). Then there are at least
available colors for
. By Lemma 2.1,
. So we can color
and
properly such that
for
. Hence, we obtain an nsd-K-coloring of G by Remark 1, a contradiction.
(5.1) Assume to the contrary that u in H is adjacent to five good 2-vertices
,
,
,
,
and one
-vertex
. By Claim 3.1 (2), it holds that
for each
. Assume that u in G is adjacent to l leaves
with
.
Suppose that
. Then
. Let
. Then
has an nsd-K-coloring by the minimality of G. When
, i.e.
, we know that there are at least
colors available for
(
). By Lemma 2.1,
. So we can color
and
properly such that
for each
, a contradiction. When
, then
. So we have
for each
. There are at least
available colors for
(
). By Lemma 2.1,
. Thus, we can color properly the edges
and
such that
, a contradiction.
Suppose that
. Let
. Then
has an nsd-K-coloring by the minimality of G. When
, i.e.
, it is evident that there are at least
colors available for
. So we get an nsd-K-coloring of G, a contradiction. When
, then
. So we have
for each
. There are at least
available colors for
. Then we get an nsd-K-coloring of G, a contradiction.
(5.2) Assume that u of H is adjacent to a deficient vertex
and two good 2-vertices
and
. By Claim 3.1, it holds that
,
and
for each
. Let
for
. Let
. Then
has an nsd-K-coloring by the minimality of G. We erase the colors on edges
. For each
, we use
to color
. Let
be the available color set for
. Then
and
. Now we consider the following polynomial:
Let
By matlab, we obtain that
. According to Lemma 2.2, we can choose
(
) such that
. Thus, we get an nsd-K-coloring of G by Remark 1, a contradiction.
Remark 2. Note that if
, then
. So
when
for any proper edge coloring of G.
Claim 3.4. Let
with
. Suppose that
.
(1)
.
(2) If
, then
.
(3) If
, then
.
(3.1) If
, then
.
(3.2) If
, then
.
Proof: (1) Assume to the contrary that u in H is adjacent to d 2-vertices
. By Claim 3.1 (2), we have
for each
. Assume that u in G is adjacent to l leaves
.
Suppose that
. Then
. Let
. Then
has an nsd-K-coloring by the minimality of G. If
. Then
. There are at least
colors available for
(
). By Lemma 2.1,
. So we can color
properly such that
for each
. So we get an nsd-K-coloring of G, a contradiction. So suppose that
. By Remark 2,
(
) for any proper edge coloring of G. Note that there are at least
available colors for
(
). Hence, we get an nsd-K-coloring of G, a contradiction.
Suppose that
. Let
. Then
has an nsd-K-coloring by the minimality of G. If
, i.e.
, then there are at least
colors available for
. So we get an nsd-K-coloring of G, a contradiction. If
, then
for each
for any proper coloring of G by Remark 2. Note that there are at least
available colors for
. Hence, we get an nsd-K-coloring of G, a contradiction.
(2) Assume that u of H is adjacent to a deficient vertex
. Let
. By Claim 3.1, it holds that
,
and
. Let
. Then
has an nsd-K-coloring by the minimality of G. There are at least
available colors for
. Hence, we can get an nsd-K-coloring of G by Remark 1, a contradiction.
(3) Assume to the contrary that u in H is adjacent to
deficient vertices
. Let
for each
. By Claim 3.1, it holds that
,
and
for
. Let
. Then
has an nsd-K-coloring by the minimality of G. We erase the colors on edges
for each
. There are at least
available colors for
(
). By Lemma 2.1,
. So we can color
properly such that
for each
. Hence, we get an nsd-K-coloring of G by Remark 1, a contradiction.
(3.1) Assume that u of H is adjacent to
2-vertices
such that
is a deficient vertex. Let
for
. By Claim 3.1, it holds that
,
and
for each
. Let
. Then
has an nsd-K-coloring by the minimality of G. Firstly, we erase the colors on edge
. For each
, we use
to color
. Let
be the available color set for
. Then
and
(
). Now we consider the following polynomial:
Let
By Lemma 2.3, we obtain that
. Thus, we get an nsd-K-coloring of G by Remark 1, a contradiction.
(3.2) Assume to the contrary that, u in H is adjacent to (
) 2-vertices
such that
are deficient vertices. Then
and
are good 2-vertices by Claim 3.4 (3). Let
for each
. By Claim 3.1, it holds that
,
for
. Consider that
. Then
has an nsd-K-coloring by the minimality of G. We erase the color on edge
for each
. There are at least
available colors for
(
), at least
available colors for
(
). By Lemma 2.1,
. So we can color
properly such that
for each
. Thus, we get an nsd-K-coloring of G by Remark 1, a contradiction.
Claim 3.5. Let
with
. If
and
, then
.
Proof: Assume that u of H is adjacent to
3−-vertices
such that
is a deficient vertex and
are 2-vertices. By Claim 3.1, it holds that
. Suppose that
for each
. Let
. Then
has an nsd-K-coloring by the minimality
of G. Since
, then we can
get
for each
. Firstly, we erase the color on edge
. There are at least
available colors for
. Thus, we obtain an nsd-K-coloring of G by Remark 1, a contradiction.
3.2. Discharging Process
In order to complete the proof of Theorem 1.1, we use the discharging method. For this aim we first define the original charge function
for each
, then
We will design several discharging rules and reassign the charges according to the rules below. Let
be the final charge. We will show that for each
,
. This leads to the following contradiction:
and it shows the nonexistence of G.
We define the discharging rules as follows:
(R1) Every 5+-vertex gives
to each adjacent bad 2-vertex;
to each adjacent weak 2-vertex;
to each adjacent good 2-vertex.
(R2) Every source vertex gives
to its sink vertex.
(R3) Every 4-vertex gives
to each adjacent 2-vertex.
(R4) Every 4+-vertex gives
to each adjacent 3-vertex.
Now we are going to show
for each
. Let
with
. By Claim 3.1 (1),
.
(1)
. According to Claim 3.3 (1), u is adjacent to at least one 5+-vertex. First, suppose that u is a bad 2-vertex. Then by (R1),
. Next, suppose that u is a weak 2-vertex. If u is adjacent to a 3-vertex, then u has two source vertices. By (R1) and (R2),
. If u is adjacent to a 4-vertex, then by (R1) and (R3),
. Finally, suppose that u is a good 2-vertex, by (R1),
.
(2)
. According to Claim 3.3 (2), u is adjacent to at least two 4+-vertex. Then by (R4),
.
(3)
. If u is adjacent to 2-vertex, then by Claim 3.2 (2),
. By (R3),
. If u is not adjacent to 2-vertex, then by (R4),
.
(4)
. It is trivial that
. Hence we have:
(1)
(4.1)
. According to Claim 3.3 (4),
. By Claim 3.3 (3),
.
Suppose that
. By Claim 3.3 (4.2),
. Furthermore, if
, then
. Suppose that
. Then
,
and
. Thus,
by (1). Suppose that
. Then
,
and
. Thus,
by (1).
Suppose that
. If
, then
and
by Claim 3.3 (3) (4.1). Thus,
. If
, then
,
and
. Thus,
by (1).
Suppose that
. Then
by (1).
(4.2)
. According to Claim 3.3 (5),
.
Suppose that
. Then we have
. By Claim 3.3 (5.2),
. Thus,
by (1).
Suppose that
. If
, then
. We have
. Thus,
by (1). If
, then
by (1).
(4.3)
. By Claim 3.3 (3),
.
(4.3.1) Suppose that
.
Suppose that
. Then by Claim 3.4 (1) and (2), we have
and
. Then
and
. Thus,
.
Suppose that
. Since
, we have
. Then by Claim 3.4 (3), we have
. If
, then
,
. Thus,
by (1). If
, then
and
. Thus,
by (1).
Suppose that
. By Claim 3.5, we know
. If
, then
. Thus,
by (1). If
, then by (1), we have
. If
, then
.
(4.3.1) Suppose that
. We have
. According to Claim 3.4 (3) and Claim 3.5, the derivation process is completely analogous to 4.3.1.
4. Conclusion
In this paper, we have studied neighbor sum distinguishing index of sparse graphs. However, there are still many graphs which are not covered here. So, for further research, we will consider the neighbor sum distinguishing edge coloring of planar graphs.