Affirmative Solutions on Local Antimagic Chromatic Number
- PDF / 1,178,630 Bytes
- 18 Pages / 439.37 x 666.142 pts Page_size
- 29 Downloads / 222 Views
(0123456789().,-volV)(0123456789().,-volV)
ORIGINAL PAPER
Affirmative Solutions on Local Antimagic Chromatic Number Gee-Choon Lau1
•
Ho-Kuen Ng2 • Wai-Chee Shiu3,4
Received: 24 September 2018 / Revised: 13 May 2020 Ó Springer Japan KK, part of Springer Nature 2020
Abstract An edge labeling of a connected graph G ¼ ðV; EÞ is said to be local antimagic if it is a bijection f : E ! f1; . . .; jEjg such that for any pair P of adjacent vertices x and y, f ðeÞ, with e ranging over f þ ðxÞ 6¼ f þ ðyÞ, where the induced vertex label f þ ðxÞ ¼ all the edges incident to x. The local antimagic chromatic number of G, denoted by vla ðGÞ, is the minimum number of distinct induced vertex labels over all local antimagic labelings of G. In this paper, we give counterexamples to the lower bound of vla ðG _ O2 Þ that was obtained in [Local antimagic vertex coloring of a graph, Graphs Combin. 33:275–285 (2017)]. A sharp lower bound of vla ðG _ On Þ and sufficient conditions for the given lower bound to be attained are obtained. Moreover, we settled Theorem 2.15 and solved Problem 3.3 in the affirmative. We also completely determined the local antimagic chromatic number of complete bipartite graphs. Keywords Local antimagic labeling Local antimagic chromatic number
Mathematics Subject Classification 05C78 05C69
The third author was supported by Tianjin Research Program of Application Foundation and Advanced Technology (No. 14JCYBJC43100) for visiting Tianjin University of Technology and Education. & Gee-Choon Lau [email protected] Ho-Kuen Ng [email protected] Wai-Chee Shiu [email protected] Extended author information available on the last page of the article
123
Graphs and Combinatorics
1 Introduction A connected graph G ¼ ðV; EÞ is said to be local antimagic if it admits a local antimagic edge labeling, i.e., a bijection f : E ! Pf1; . . .; jEjg such that the induced f ðeÞ (with e ranging over all the vertex labeling f þ : V ! Z given by f þ ðxÞ ¼ edges incident to x) has the property that any two adjacent vertices have distinct induced vertex labels. The number of distinct induced vertex labels under f is denoted by c(f), and is called the color number of f. The local antimagic chromatic number of G, denoted by vla ðGÞ, is minfcðf Þ : f is a local antimagic labeling of Gg. In [3], Haslegrave proved that the local antimagic chromatic number is well-defined for every connected graph other than K2 . Thus, for every connected graph G 6¼ K2 , vla ðGÞ vðGÞ, the chromatic number of G. For any graph G, the graph H ¼ G _ On , n 1, is defined by VðHÞ ¼ VðGÞ [ fvi : 1 i ng and EðHÞ ¼ EðGÞ [ fuvi : u 2 VðGÞg. In [1, Theorem 2.16], it was claimed that for any G with order m 4, vla ðGÞ þ 1 if m is even, vla ðGÞ þ 1 vla ðG _ O2 Þ vla ðGÞ þ 2 if m is odd : In Sect. 2, we give counterexamples to the above lower bound for each m 3. A sharp lower bound is then given. Moreover, sufficient conditions for the above lower bound to be attained are also presented. In Sect. 3, we settled [1, Theorem 2.15] and sol
Data Loading...
