Search

It is known that null graphs and 1-regular graphs are the only regular graphs without local antimagic chromatic number. In this paper, we proved that the join of 1-regular graph and a null graph has local antimagic chromatic number is 3. Consequently, we also obtained many families of (possibly disconnected or regular) bipartite and tripartite graph with local antimagic chromatic number 3.

For a graph $G(V,E)$ of size $q$, a bijection $f : E(G) \to [1,q]$ is a local antimagc labeling if it induces a vertex labeling $f^+ : V(G) \to \mathbb{N}$ such that $f^+(u) \ne f^+(v)$, where $f^+(u)$ is the sum of all the incident edge label(s) of $u$, for every edge $uv \in E(G)$. In this paper, we make use of matrices of fixed sizes to construct several families of infinitely many tripartite graphs with local antimagic chromatic number 3., Comment: arXiv admin note: text overlap with arXiv:2408.04942

It is known that null graphs and 1-regular graphs are the only regular graphs without local antimagic chromatic number. In this paper, we use matrices of size $(2m+1) \times (2k+1)$ to completely determine the local antimagic chromatic number of the join of null graphs, $O_m, m\ge 1,$ and 1-regular graphs of odd components, $(2k+1)P_2$, $k\ge 1$. Consequently, we obtained infinitely many (possibly disconnected or regular) tripartite graphs with local antimagic chromatic number 3., Comment: 15 pages, 8 figures

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 $\chi_{la}(G)$, is the minimum number of distinct induced vertex labels over all local antimagic labelings of $G$. Suppose $\chi_{la}(G)=\chi_{la}(H)$ and $G_H$ is obtained from $G$ and $H$ by merging some vertices of $G$ with some vertices of $H$ bijectively. In this paper, we give ways to construct matrices with integers in $[1,10k]$, $k\ge 1$, that meet certain properties. Consequently, we obtained many families of (disconnected) bipartite (and tripartite) graphs of size $10k$ with local antimagic chromatic number 3.

An edge labeling of a connected graph $G = (V, E)$ is said to be local antimagic if there 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 $\chi_{la}(G)$, is the minimum number of distinct induced vertex labels over all local antimagic labelings of $G$. In this paper, we give three ways to construct a $(3m+2)\times (2k+1)$ matrix that meets certain properties for $m=1,3$ and $k\ge 1$. Consequently, we obtained many (disconnected) graphs of size $(3m+2)(2k+1)$ with local antimagic chromatic number 3.

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 $\chi_{la}(G)$, is the minimum number of distinct induced vertex labels over all local antimagic labelings of $G$. In this paper, we characterize $s$-bridge graphs with local antimagic chromatic number 2.

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 $\chi(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$.

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 $\chi_{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 $\chi_{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 $\chi_{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) $\chi_{la}(G)=\chi(G)=k$, and (ii) $\chi_{la}(G)=\chi(G)+1=k$ for each possible $r,p,k$.

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 $\chi_{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.

An edge labeling of a 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 of $x$ is $f^+(x)= \sum_{e\in E(x)} f(e)$ ($E(x)$ is the set of edges incident to $x$). The local antimagic chromatic number of $G$, denoted by $\chi_{la}(G)$, is the minimum number of distinct induced vertex labels over all local antimagic labelings of $G$. In this paper, several sufficient conditions to determine the local antimagic chromatic number of the join of graphs are obtained. We then determine the exact value of the local antimagic chromatic number of many join graphs., Comment: 14 pages, submitted for journal publication

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., Comment: Submitted to Special Issue "Graph Labelings and Their Applications" to be published by Symmetry

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 $\chi_{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 $\chi_{la}\ge 3$. A necessary and sufficient condition for a graph to have $\chi_{la}=2$ is then obtained; (ii) give a sufficient condition for every circulant graph of even order to have $\chi_{la} = 3$; (iii) construct infinitely many bipartite and tripartite graphs with $\chi_{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 $\chi_{la} = 2,3$. The work of this paper suggests many open problems on the local antimagic chromatic number of bipartite and tripartite graphs., Comment: A work that produces infinitely many bipartite graphs with local antimagic chromatic number is 2 or 3, and infinitely many tripartite graphs with local antimagic chromatic number is 3. Many open problems on bipartite and tripartite graphs are suggested

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 $\chi_{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 \chi_{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 $\chi_{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 $\chi_{la} = d+1$., Comment: 25 pages

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 $\chi_{la}(G)$, is the minimum number of distinct induced vertex labels over all local antimagic labelings of $G$. Let $\chi(G)$ be the chromatic number of $G$. In this paper, sharp upper and lower bounds of $\chi_{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 \chi(G) - 1$ pendant vertices and $\chi_{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 $\chi_{la}(T_k) = k+1$., Comment: 6 page, 3 figures, a new short paper that gives tight upper and lower bounds with sufficient conditions for the bounds to be equal

A $(p,q,r)$-board that has $pq+pr+qr$ squares consists of a $(p,q)$-, a $(p,r)$-, and a $(q,r)$-rectangle. Let $S$ be the set of the squares. Consider a bijection $f : S \to [1,pq+pr+qr]$. Firstly, for $1 \le i \le p$, let $x_i$ be the sum of all the $q+r$ integers in the $i$-th row of the $(p,q+r)$-rectangle. Secondly, for $1 \le j \le q$, let $y_j$ be the sum of all the $p+r$ integers in the $j$-th row of the $(q,p+r)$-rectangle. Finally, for $1\le k\le r$, let $z_k$ be the the sum of all the $p+q$ integers in the $k$-th row of the $(r,p+q)$-rectangle. Such an assignment is called a $(p,q,r)$-design if $\{x_i : 1\le i\le p\}=\{c_1\}$ for some constant $c_1$, $\{y_j : 1\le j\le q\}=\{c_2\}$ for some constant $c_2$, and $\{z_k : 1\le k\le r\}=\{c_3\}$ for some constant $c_3$. A $(p,q,r)$-board that admits a $(p,q,r)$-design is called (1) Cartesian tri-magic if $c_1$, $c_2$ and $c_3$ are all distinct; (2) Cartesian bi-magic if $c_1$, $c_2$ and $c_3$ assume exactly 2 distinct values; (3) Cartesian magic if $c_1 = c_2 = c_3$ (which is equivalent to supermagic labeling of $K(p,q,r)$). Thus, Cartesian magicness is a generalization of magic rectangles into 3-dimensional space. In this paper, we study the Cartesian magicness of various $(p,q,r)$-board by matrix approach involving magic squares or rectangles. In Section~2, we obtained various sufficient conditions for $(p,q,r)$-boards to admit a Cartesian tri-magic design. In Sections~3 and~4, we obtained many necessary and (or) sufficient conditions for various $(p,q,r)$-boards to admit (or not admit) a Cartesian bi-magic and magic design. In particular, it is known that $K(p,p,p)$ is supermagic and thus every $(p,p,p)$-board is Cartesian magic. We gave a short and simpler proof that every $(p,p,p)$-board is Cartesian magic.

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 $\chi_{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 $\chi_{la}(H)\le \chi_{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.

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 $\chi_{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.]., Comment: Final version accepted by Iran. J. Math. Sci Inform

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 $\chi_{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 $\chi_{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 $\chi_{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., Comment: arXiv admin note: text overlap with arXiv:1805.04801