Neighbor Sum Distinguishing Total Colorings of Corona of Subcubic Graphs
- PDF / 369,728 Bytes
- 8 Pages / 439.37 x 666.142 pts Page_size
- 7 Downloads / 215 Views
Neighbor Sum Distinguishing Total Colorings of Corona of Subcubic Graphs Aijun Dong1
· Wenwen Zhang1 · Xiang Tan2
Received: 14 January 2020 / Revised: 16 June 2020 / Accepted: 5 October 2020 © Malaysian Mathematical Sciences Society and Penerbit Universiti Sains Malaysia 2020
Abstract A proper [k]-total coloring c of a graph G is a proper total coloring c of G using colors of the set [k] = {1, 2, . . . , k}. Let (u) denote the sum of the color on a vertex u and the colors on all the edges incident with u. For each edge uv ∈ E(G), if (u) = (v), then we say the coloring distinguishes adjacent vertices by sum and call it a neighbor sum distinguishing total coloring of G. By tndi (G), we denote the minimal value of k in such a coloring of G. It has been conjectured by Pil´sniak et al. that (G) + 3 colors enable the existence of a neighbor sum distinguishing total coloring. In this paper, we consider the neighbor sum distinguishing total coloring of corona product G ◦ H and obtain that tndi (G ◦ H ) ≤ (G ◦ H ) + 3. Keywords Total coloring · Neighbor sum distinguishing coloring · Subcubic graphs Mathematics Subject Classification 05C15
Communicated by Sanming Zhou. This work was supported by China Postdoctoral Science Foundation Funded Project (Grant No. 2014M561909); the Nature Science Foundation of Shandong Province of China (Grant Nos. ZR2014AM028, ZR2017BA009).
B
Aijun Dong [email protected] Wenwen Zhang [email protected] Xiang Tan [email protected]
1
School of Data and Computer Science, Shandong Women’s University, Jinan 250300, China
2
School of Mathematic and Quantitative Economics, Shandong University of Finance and Economics, Jinan 250014, China
123
A. Dong et al.
1 Introduction The terminology and notation used but undefined in this paper can be found in [1]. Let G = (V , E) be a graph. We use V (G), E(G), (G) and δ(G) to denote the vertex set, edge set, maximum degree and minimum degree of G, respectively. Let N G (u) be the set of neighbors of u in the graph G. For two simple graphs G and H , we use n g and n h to denote the number of vertices in G and H , respectively, i.e., n g = |V (G)| and n h = |V (H )|. Let [k] be a set of colors where [k] = {1, 2, . . . , k}, and let c be a total coloring of G forwhich c : E(G) ∪ V (G) → [k]. For each vertex u ∈ V (G), let (u) = c(u) + u∈e c(e) (resp. S(v) = {c(uv)|uv ∈ E(G)} ∪ {c(v)}) denote the sum (resp. the set) of the colors on the vertex u and the edges which are incident with u. If the coloring c is proper, then we call the coloring c such that (v) = (u) (resp. S(u) = S(v)) for each edge uv ∈ E(G) a neighbor sum distinguishing total coloring (resp. neighbor ver tex distinguishing total coloring) of G, or a N S DT C (resp. N V DT C)of G for simplicity. By tndi (G) (resp. tndi(G)), we denote the smallest value k such that G has a neighbor sum (resp. vertex) distinguishing [k]-total coloring of G. It is easy to observe that if two vertices are distinguished by sum, then they are also distinguished by sets, but not necessar
Data Loading...
