Neighbor Sum Distinguishing Index of Sparse Graphs
- PDF / 315,641 Bytes
- 18 Pages / 510.236 x 737.008 pts Page_size
- 99 Downloads / 225 Views
Acta Mathematica Sinica, English Series Springer-Verlag GmbH Germany & The Editorial Office of AMS 2020
Neighbor Sum Distinguishing Index of Sparse Graphs Ji Hui WANG
Bao Jian QIU
School of Mathematical Sciences, University of Jinan, Jinan 250022, P. R. China E-mail : [email protected] [email protected]
Jian Sheng CAI School of Mathematics and Information Sciences, Weifang University, Weifang 261061, P. R. China E-mail : [email protected] Abstract A proper k-edge coloring of a graph G is an assignment of one of k colors to each edge of G such that there are no two edges with the same color incident to a common vertex. Let f (v) denote the sum of colors of the edges incident to v. A k-neighbor sum distinguishing edge coloring of G is a proper k-edge coloring of G such that for each edge uv ∈ E(G), f (u) = f (v). By χ (G), we denote the smallest value k in such a coloring of G. Let mad (G) denote the maximum average degree of a and Δ(G) ≥ 8 admits graph G. In this paper, we prove that every normal graph with mad (G) < 10 3 a (Δ(G) + 2)-neighbor sum distinguishing edge coloring. Our approach is based on the Combinatorial Nullstellensatz and discharging method. Keywords Proper edge coloring, neighbor sum distinguishing edge coloring, maximum average degree, Combinatorial Nullstellensatz MR(2010) Subject Classification
1
05C15
Introduction
In this paper we only consider undirected, finite and simple graphs. Some notations and terminology used but not defined can be found in [4]. We use V (G), E(G), δ(G) and Δ(G) to denote the set of vertices, the set of edges, minimum degree and maximum degree of G, respectively. Denote by NG (v) the set of neighbors of the vertex v in G. Let dG (v) or simply d(v), denote the degree of v in G. A vertex v is called an l-vertex if d(v) = l. Similarly, an l+ -vertex (l− -vertex) is a vertex with d(v) ≥ l (d(v) ≤ l). We call a 1-vertex a leaf. A 2-vertex v which is adjacent to a 3− -vertex, is called a bad 2-vertex. Otherwise, we call v a good 2-vertex. The average degree ad(G) of G is defined as ad(G) = 2|E(G)| |V (G)| . The maximum average degree mad (G) of G is the maximum average degree of its subgraphs. The girth of a graph G is the length of a shortest cycle in G, denoted by g(G). Given a positive integer k, a proper k-edge coloring c of G is a mapping c : E → {1, 2, . . . , k} such that any two adjacent edges are assigned to different integer. We use c(uv) to denote the color on edge uv, and C(v) denotes the set of the colors of the incident edges of vertex v, Received January 26, 2019, revised July 14, 2019, accepted September 12, 2019 Supported by the Natural Science Foundation of Shandong Provence (Grant Nos. ZR2018BA010, ZR2016AM01) and the National Natural Science Foundation of China (Grant No. 11571258)
Wang J. H. et al.
674
i.e., C(v) = {c(uv) | uv ∈ E(G)}. A proper k-edge coloring c is called neighbor distinguishing k-edge coloring if for any edge uv ∈ E(G), C(u) = C(v). The smallest k such that G has a neighbor distinguishing k-edge coloring, is called the neighbor
Data Loading...
