BZPEER

preprint2022arXiv

A note on local antimagic chromatic number of lexicographic product graphs

Let $G = (V,E)$ be a connected simple graph. A bijection $f: E \rightarrow \{1,2,\ldots,|E|\}$ is called a local antimagic labeling of $G$ if $f^+(u) \neq f^+(v)$ holds for any two adjacent vertices $u$ and $v$ , where $f^+(u) = \sum_{e\in E(u)} f(e)$ and $E(u$ ) is the set of edges incident to $u$ . A graph $G$ is called local antimagic if $G$ admits at least a local antimagic labeling. The local antimagic chromatic number, denoted $χ_{la}(G)$ , is the minimum number of induced colors taken over local antimagic labelings of $G$ . Let $G$ and $H$ be two disjoint graphs. The graph $G[H]$ is obtained by the lexicographic product of $G$ and $H$ . In this paper, we obtain sufficient conditions for $χ_{la}(G[H])\leq χ_{la}(G)χ_{la}(H)$ . Consequently, we give examples of $G$ and $H$ such that $χ_{la}(G[H]) = χ(G)χ(H)$ , where $χ(G)$ is the chromatic number of $G$ . We conjecture that (i) there are infinitely many graphs $G$ and $H$ such that $χ_{la}(G[H])=χ_{la}(G)χ_{la}(H) = χ(G)χ(H)$ , and (ii) for $k\ge 1$ , $χ_{la}(G[H]) = χ(G)χ(H)$ if and only if $χ(G)χ(H) = 2χ(H) + \lceil\frac{χ(H)}{k}\rceil$ , where $2k+1$ is the length of a shortest odd cycle in $G$ .

preprint2022arXiv

On join product and local antimagic chromatic number of regular graphs

Let $G = (V,E)$ be a connected simple graph of order $p$ and size $q$ . A graph $G$ is called local antimagic if $G$ admits a local antimagic labeling. A bijection $f : E \to \{1,2,\ldots,q\}$ is called a local antimagic labeling of $G$ if for any two adjacent vertices $u$ and $v$ , we have $f^+(u) \ne f^+(v)$ , where $f^+(u) = \sum_{e\in E(u)} f(e)$ , and $E(u)$ is the set of edges incident to $u$ . Thus, any local antimagic labeling induces a proper vertex coloring of $G$ if vertex $v$ is assigned the color $f^+(v)$ . The local antimagic chromatic number, denoted $χ_{la}(G)$ , is the minimum number of induced colors taken over local antimagic labeling of $G$ . Let $G$ and $H$ be two vertex disjoint graphs. The join graph of $G$ and $H$ , denoted $G \vee H$ , is the graph $V(G\vee H) = V(G) \cup V(H)$ and $E(G\vee H) = E(G) \cup E(H) \cup \{uv \,|\, u\in V(G), v \in V(H)\}$ . In this paper, we show the existence of non-complete regular graphs with arbitrarily large order, regularity and local antimagic chromatic numbers.

preprint2022arXiv

On local antimagic chromatic number of a corona product graph

In this paper, we provide a correct proof for the lower bounds of the local antimagic chromatic number of the corona product of friendship and fan graphs with null graph respectively as in [On local antimagic vertex coloring of corona products related to friendship and fan graph, {\it Indon. J. Combin.}, 5(2) (2021) 110--121]. Consequently, we obtained a sharp lower bound that gives the exact local antimagic chromatic number of the corona product of friendship and null graph.

preprint2022arXiv

On local antimagic chromatic number of graphs with cut-vertices

An edge labeling of a connected graph $G = (V, E)$ is said to be local antimagic if it is a bijection $f:E \to\{1,\ldots ,|E|\}$ such that for any pair of adjacent vertices $x$ and $y$ , $f^+(x)\not= f^+(y)$ , where the induced vertex label $f^+(x)= \sum f(e)$ , with $e$ ranging over all the edges incident to $x$ . The local antimagic chromatic number of $G$ , denoted by $χ_{la}(G)$ , is the minimum number of distinct induced vertex labels over all local antimagic labelings of $G$ . In this paper, the sharp lower bound of the local antimagic chromatic number of a graph with cut-vertices given by pendants is obtained. The exact value of the local antimagic chromatic number of many families of graphs with cut-vertices (possibly given by pendant edges) are also determined. Consequently, we partially answered Problem 3.1 in [Local antimagic vertex coloring of a graph, {\it Graphs and Combin.}, {\bf33} (2017), 275--285.].

preprint2022arXiv

On local antimagic chromatic number of lexicographic product graphs

Let $G = (V,E)$ be a connected simple graph of order $p$ and size $q$ . A graph $G$ is called local antimagic if $G$ admits a local antimagic labeling. A bijection $f : E \to \{1,2,\ldots,q\}$ is called a local antimagic labeling of $G$ if for any two adjacent vertices $u$ and $v$ , we have $f^+(u) \ne f^+(v)$ , where $f^+(u) = \sum_{e\in E(u)} f(e)$ , and $E(u)$ is the set of edges incident to $u$ . Thus, any local antimagic labeling induces a proper vertex coloring of $G$ if vertex $v$ is assigned the color $f^+(v)$ . The local antimagic chromatic number, denoted $χ_{la}(G)$ , is the minimum number of induced colors taken over local antimagic labeling of $G$ . Let $G$ and $H$ be two vertex disjoint graphs. The {\it lexicographic product} of $G$ and $H$ , denoted $G[H]$ , is the graph with vertex set $V(G) \times V(H)$ , and $(u,u')$ is adjacent to $(v,v')$ in $G[H]$ if $(u,v)\in E(G)$ or if $u=v$ and $u'v'\in E(H)$ . In this paper, we obtained sharp upper bound of $χ_{la}(G[O_n])$ where $O_n$ is a null graph of order $n\ge 1$ . Sufficient conditions for even regular bipartite and tripartite graphs $G$ to have $χ_{la}(G)=3$ are also obtained. Consequently, we successfully determined the local antimagic chromatic number of infinitely many (connected and disconnected) regular graphs that partially support the existence of $r$ -regular graph $G$ of order $p$ such that (i) $χ_{la}(G)=χ(G)=k$ , and (ii) $χ_{la}(G)=χ(G)+1=k$ for each possible $r,p,k$ .

preprint2022arXiv

On local antimagic total labeling of amalgamation graphs

Let $G = (V,E)$ be a connected simple graph of order $p$ and size $q$ . A graph $G$ is called local antimagic (total) if $G$ admits a local antimagic (total) labeling. A bijection $g : E \to \{1,2,\ldots,q\}$ is called a local antimagic labeling of $G$ if for any two adjacent vertices $u$ and $v$ , we have $g^+(u) \ne g^+(v)$ , where $g^+(u) = \sum_{e\in E(u)} g(e)$ , and $E(u)$ is the set of edges incident to $u$ . Similarly, a bijection $f:V(G)\cup E(G)\to \{1,2,\ldots,p+q\}$ is called a local antimagic total labeling of $G$ if for any two adjacent vertices $u$ and $v$ , we have $w_f(u)\ne w_f(v)$ , where $w_f(u) = f(u) + \sum_{e\in E(u)} f(e)$ . Thus, any local antimagic (total) labeling induces a proper vertex coloring of $G$ if vertex $v$ is assigned the color $g^+(v)$ (respectively, $w_f(u)$ ). The local antimagic (total) chromatic number, denoted $χ_{la}(G)$ (respectively $χ_{lat}(G)$ ), is the minimum number of induced colors taken over local antimagic (total) labeling of $G$ . In this paper, we determined $χ_{lat}(G)$ where $G$ is the amalgamation of complete graphs.

preprint2022arXiv

Sudoku Number of Graphs

We introduce a new concept in graph coloring motivated by the popular Sudoku puzzle. Let $G=(V,E)$ be a graph of order $n$ with chromatic number $χ(G)=k$ and let $S\subseteq V.$ Let $\mathscr C_0$ be a $k$ -coloring of the induced subgraph $G[S].$ The coloring $\mathscr C_0$ is called an extendable coloring if $\mathscr C_0$ can be extended to a $k$ -coloring of $G.$ We say that $\mathscr C_0$ is a Sudoku coloring of $G$ if $\mathscr C_0$ can be uniquely extended to a $k$ -coloring of $G.$ The smallest order of such an induced subgraph $G[S]$ of $G$ which admits a Sudoku coloring is called the Sudoku number of $G$ and is denoted by $sn(G).$ In this paper we initiate a study of this parameter. We first show that this parameter is related to list coloring of graphs. In Section 2, basic properties of Sudoku coloring that are related to color dominating vertices, chromatic numbers and degree of vertices, are given. Particularly, we obtained necessary conditions for $\mathscr C_0$ being uniquely extendable, and for $\mathscr C_0$ being a Sudoku coloring. In Section 3, we determined the Sudoku number of various familes of graphs. Particularly, we showed that a connected graph $G$ has $sn(G)=1$ if and only if $G$ is bipartite. Consequently, every tree $T$ has $sn(T)=1$ . Moreover, a graph $G$ with small chromatic number may have arbitrarily large Sudoku number. Extendable coloring and Sudoku coloring are nice tools for providing a $k$ -coloring of $G$ .

preprint2021arXiv

Graphs With Minimal Strength

For any graph $G$ of order $p$ , a bijection $f: V(G)\to [1,p]$ is called a numbering of the graph $G$ of order $p$ . The strength $str_f(G)$ of a numbering $f: V(G)\to [1,p]$ of $G$ is defined by $str_f(G) = \max\{f(u)+f(v)\; |\; uv\in E(G)\},$ and the strength $str(G)$ of a graph $G$ itself is $str(G) = \min\{str_f(G)\;|\; f \mbox{ is a numbering of } G\}.$ A numbering $f$ is called a strength labeling of $G$ if $str_f(G)=str(G)$ . In this paper, we obtained a sufficient condition for a graph to have $str(G)=|V(G)|+\d(G)$. Consequently, many questions raised in [Bounds for the strength of graphs, {\it Aust. J. Combin.} {\bf72(3)}, (2018) 492--508] and [On the strength of some trees, {\it AKCE Int. J. Graphs Comb.} (Online 2019) doi.org/10.1016/j.akcej.2019.06.002] are solved. Moreover, we showed that every graph $G$ either has $str(G)=|V(G)|+\d(G)$ or is a proper subgraph of a graph $H$ that has $str(H) = |V(H)| + \d(H)$ with $\d(H)=\d(G)$. Further, new good lower bounds of $str(G)$ are also obtained. Using these, we determined the strength of 2-regular graphs and obtained new lower bounds of $str(Q_n)$ for various $n$ , where $Q_n$ is the $n$ -regular hypercube.

preprint2020arXiv

Affirmative Solutions On Local Antimagic Chromatic Number

An edge labeling of a connected graph $G = (V, E)$ is said to be local antimagic if it is a bijection $f:E \to\{1,\ldots ,|E|\}$ such that for any pair of adjacent vertices $x$ and $y$ , $f^+(x)\not= f^+(y)$ , where the induced vertex label $f^+(x)= \sum f(e)$ , with $e$ ranging over all the edges incident to $x$ . The local antimagic chromatic number of $G$ , denoted by $χ_{la}(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 $χ_{la}(G \vee O_2)$ that was obtained in [Local antimagic vertex coloring of a graph, Graphs and Combin., 33 : 275 - 285 (2017)]. A sharp lower bound of $χ_{la}(G\vee O_n)$ 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.

preprint2020arXiv

Approaches Which Output Infinitely Many Graphs With Small Local Antimagic Chromatic Number

An edge labeling of a connected graph $G = (V, E)$ is said to be local antimagic if it is a bijection $f:E \to\{1,\ldots ,|E|\}$ such that for any pair of adjacent vertices $x$ and $y$ , $f^+(x)\not= f^+(y)$ , where the induced vertex label $f^+(x)= \sum f(e)$ , with $e$ ranging over all the edges incident to $x$ . The local antimagic chromatic number of $G$ , denoted by $χ_{la}(G)$ , is the minimum number of distinct induced vertex labels over all local antimagic labelings of $G$ . In this paper, we (i) give a sufficient condition for a graph with one pendant to have $χ_{la}\ge 3$ . A necessary and sufficient condition for a graph to have $χ_{la}=2$ is then obtained; (ii) give a sufficient condition for every circulant graph of even order to have $χ_{la} = 3$ ; (iii) construct infinitely many bipartite and tripartite graphs with $χ_{la} = 3$ by transformation of cycles; (iv) apply transformation of cycles to obtain infinitely many one-point union of regular (possibly circulant) or bi-regular graphs with $χ_{la} = 2,3$ . The work of this paper suggests many open problems on the local antimagic chromatic number of bipartite and tripartite graphs.

preprint2020arXiv

On Integer Sequences Associated To Two Distinct Sums

In this note, we show the existence of integer sequences of lengths at least 3 (except 7) such that for every integer in position $i\equiv 1\pmod{4}$ (respectively position $j\equiv 3\pmod{4}$ ), counting from left to right, the sum of the integer and the adjacent integer(s) has a constant sum $x$ (respectively $y$ ) with $x\ne y$ .

preprint2020arXiv

On Local Antimagic Chromatic Number of Spider Graphs

An edge labeling of a connected graph $G = (V,E)$ is said to be local antimagic if it is a bijection $f : E \to \{1, . . . , |E|\}$ such that for any pair of adjacent vertices $x$ and $y$ , $f^+(x) \ne f^+(y)$ , where the induced vertex label $f^+(x) = \sum f(e)$ , with $e$ ranging over all the edges incident to $x$ . The local antimagic chromatic number of $G$ , denoted by $χ_{la}(G)$ , is the minimum number of distinct induced vertex labels over all local antimagic labelings of $G$ . In this paper, we first show that a $d$ -leg spider graph has $d+1\le χ_{la}\le d+2$ . We then obtain many sufficient conditions such that both the values are attainable. Finally, we show that each 3-leg spider has $χ_{la} = 4$ if not all legs are of odd length. We conjecture that almost all $d$ -leg spiders of size $q$ that satisfies $d(d+1) \le 2(2q-1)$ with each leg length at least 2 has $χ_{la} = d+1$ .

preprint2020arXiv

On number of pendants in local antimagic chromatic number

An edge labeling of a connected graph $G = (V, E)$ is said to be local antimagic if it is a bijection $f:E \to\{1,\ldots ,|E|\}$ such that for any pair of adjacent vertices $x$ and $y$ , $f^+(x)\not= f^+(y)$ , where the induced vertex label $f^+(x)= \sum f(e)$ , with $e$ ranging over all the edges incident to $x$ . The local antimagic chromatic number of $G$ , denoted by $χ_{la}(G)$ , is the minimum number of distinct induced vertex labels over all local antimagic labelings of $G$ . Let $χ(G)$ be the chromatic number of $G$ . In this paper, sharp upper and lower bounds of $χ_{la}(G)$ for $G$ with pendant vertices, and sufficient conditions for the bounds to equal, are obtained. Consequently, for $k\ge 1$ , there are infinitely many graphs with $k \ge χ(G) - 1$ pendant vertices and $χ_{la}(G) = k+1$ . We conjecture that every tree $T_k$ , other than certain caterpillars, spiders and lobsters, with $k\ge 1$ pendant vertices has $χ_{la}(T_k) = k+1$ .

preprint2018arXiv

On local antimagic chromatic number of cycle-related join graphs

An edge labeling of a connected graph $G = (V, E)$ is said to be local antimagic if it is a bijection $f:E \to\{1,\ldots ,|E|\}$ such that for any pair of adjacent vertices $x$ and $y$ , $f^+(x)\not= f^+(y)$ , where the induced vertex label $f^+(x)= \sum f(e)$ , with $e$ ranging over all the edges incident to $x$ . The local antimagic chromatic number of $G$ , denoted by $χ_{la}(G)$ , is the minimum number of distinct induced vertex labels over all local antimagic labelings of $G$ . In this paper, several sufficient conditions for $χ_{la}(H)\le χ_{la}(G)$ are obtained, where $H$ is obtained from $G$ with a certain edge deleted or added. We then determined the exact value of the local antimagic chromatic number of many cycle related join graphs.

preprint2012arXiv

On the k-edge magic graphs

Let $G$ be a graph with vertex set V and edge set E such that |V| = p and |E| = q. For integers k\geq 0, define an edge labeling f : E \rightarrow \{k,k+1,....,k+q-1\} and define the vertex sum for a vertex $v$ as the sum of the labels of the edges incident to v. If such an edge labeling induces a vertex labeling in which every vertex has a constant vertex sum (mod p), then G is said to be k-edge magic (k-EM). In this paper, we (i) show that all the maximal outerplanar graphs of order p = 4; 5; 7 are k-EM if and only if k\equiv 2 (mod p); (ii) obtain all the maximal outerplanar graphs that are k-EM for k = 3; 4; and (iii) characterize all (p; p-h)-graph that are k-EM for h\geq 0. We conjecture that all maximal outerplanar graphs of prime order p are k-EM if and only if k \equiv 2 (mod p).

Gee-Choon Lau

Research overview

Is this your work?

15 publications

A note on local antimagic chromatic number of lexicographic product graphs

On join product and local antimagic chromatic number of regular graphs

On local antimagic chromatic number of a corona product graph

On local antimagic chromatic number of graphs with cut-vertices

On local antimagic chromatic number of lexicographic product graphs

On local antimagic total labeling of amalgamation graphs

Sudoku Number of Graphs

Graphs With Minimal Strength

Affirmative Solutions On Local Antimagic Chromatic Number

Approaches Which Output Infinitely Many Graphs With Small Local Antimagic Chromatic Number

On Integer Sequences Associated To Two Distinct Sums

On Local Antimagic Chromatic Number of Spider Graphs

On number of pendants in local antimagic chromatic number

On local antimagic chromatic number of cycle-related join graphs

On the k-edge magic graphs

See the researcher in context

Building this map preview