Browsing by Subject "join product"

Now showing 1 - 5 of 5

Access status: Open Access ,
Every graph is local antimagic total and its applications
(Wydawnictwa AGH, 2023) Lau, Gee-Choon; Schaffer, Karl; Shiu, Wai Chee
Let $G=(V,E)$ be a 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) \neq 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)\neq 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 $\chi_{lat}(G)$ (respectively $\chi_{lat}(G)$), is the minimum number of induced colors taken over local antimagic (total) labeling of $G$. We provide a short proof that every graph $G$ is local antimagic total. The proof provides sharp upper bound to $\chi_{lat}(G)$. We then determined the exact $\chi_{lat}(G)$, where $G$ is a complete bipartite graph, a path, or the Cartesian product of two cycles. Consequently, the $\chi_{la}(G\vee K_1)$ is also obtained. Moreover, we determined the $\chi_{la}(G\vee K_1)$ and hence the $\chi_{lat}(G)$ for a class of 2-regular graphs $G$ (possibly with a path). The work of this paper also provides many open problems on $\chi_{lat}(G)$. We also conjecture that each graph $G$ of order at least 3 has $\chi_{lat}(G)\leq \chi_{la}(G)$.
Access status: Open Access ,
On the crossing numbers of join products of five graphs of order six with the discrete graph
(Wydawnictwa AGH, 2020) Staš, Michal
The main purpose of this article is broaden known results concerning crossing numbers for join of graphs of order six. We give the crossing number of the join product $G^{\ast}+D_{n}$, where the disconnected graph $G^{\ast}$ of order six consists of one isolated vertex and of one edge joining two nonadjacent vertices of the $5$-cycle. In our proof, the idea of cyclic permutations and their combinatorial properties will be used. Finally, by adding new edges to the graph $G^{\ast}$, the crossing numbers of $G_{i}+D_{n}$ for four other graphs $G_{i}$ of order six will be also established.
Access status: Open Access ,
On the crossing numbers of join products of W4+Pn and W4+Cn
(Wydawnictwa AGH, 2021) Staš, Michal; Valiska, Juraj
The crossing number $cr(G)$ of a graph $G$ is the minimum number of edge crossings over all drawings of $G$ in the plane. The main aim of the paper is to give the crossing number of the join product $W_{4}+P_{n}$ and $W_{4}+C_{n}$ for the wheel $W_4$ on five vertices, where $P_n$ and $C_n$ are the path and the cycle on $n$ vertices, respectively. Yue et al. conjectured that the crossing number of $W_{m}+C_{n}$ is equal to $Z(m+1)Z(n)+(Z(m)-1) \big \lfloor \frac{n}{2} \big \rfloor + n+ \big\lceil\frac{m}{2}\big\rceil +2$, for all $m,n \geq 3$, and where the Zarankiewicz's number $Z(n)=\big \lfloor \frac{n}{2} \big \rfloor \big \lfloor \frac{n-1}{2} \big \rfloor$ is defined for $n \geq 1$. Recently, this conjecture was proved for $W_{3}+C_{n}$ by Klešč. We establish the validity of this conjecture for $W_{4}+C_{n}$ and we also offer a new conjecture for the crossing number of the join product $W_{m}+P_{n}$ for $m \geq 3$ and $n \geq 2$.
Access status: Open Access ,
The crossing numbers of join products of four graphs of order five with paths and cycles
(Wydawnictwa AGH, 2023) Staš, Michal; Timková, Mária
The crossing number $\mathrm{cr}(G)$ of a graph $G$ is the minimum number of edge crossings over all drawings of $G$ in the plane. In the paper, we extend known results concerning crossing numbers of join products of four small graphs with paths and cycles. The crossing numbers of the join products $G^\ast + P_n$ and $G^\ast + C_n$ for the disconnected graph $G^\ast$ consisting of the complete tripartite graph $K_{1,1,2}$ and one isolated vertex are given, where $P_n$ and $C_n$ are the path and the cycle on $n$ vertices, respectively. In the paper also the crossing numbers of $H^{\ast}+P_{n}$ and $H^{\ast}+C_{n}$ are determined, where $H^{\ast}$ is isomorphic to the complete tripartite graph $K_{1,1,3}$. Finally, by adding new edges to the graphs $G^\ast$ and $H^\ast$, we are able to obtain crossing numbers of join products of two other graphs $G_1$ and $H_1$ with paths and cycles.
Access status: Open Access ,
The crossing numbers of join products of paths with three graphs of order five
(Wydawnictwa AGH, 2022) Staš, Michal; Švecová, Mária
The main aim of this paper is to give the crossing number of the join product $G^\ast+P_n$ for the disconnected graph $G^\ast$ of order five consisting of the complete graph $K_4$ and one isolated vertex, where $P_n$ is the path on n vertices. The proofs are done with the help of a lot of well-known exact values for the crossing numbers of the join products of subgraphs of the graph $G^\ast$ with the paths. Finally, by adding new edges to the graph $G^\ast$, we are able to obtain the crossing numbers of the join products of two other graphs with the path $P_n$.