Browsing by Subject "Cartesian 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: Restricted ,
Indeks rozróżniający produktowych grafów przeliczalnych
(Data obrony: 2016-10-10) Ryngier, Angelika
Wydział Matematyki Stosowanej
Access status: Restricted ,
Liczba rozróżniająca grafów produktowych
(Data obrony: 2015-07-02) Bukowska, Anna
Wydział Matematyki Stosowanej
Access status: Open Access ,
Metric dimension of Andrásfai graphs
(Wydawnictwa AGH, 2019) Pejman, S. Batool; Payrovi, Shiroyeh; Behtoei, Ali
A set $W\subseteq V(G)$ is called a resolving set, if for each pair of distinct vertices $u,v \in V(G)$ there exists $t \in W$ such that $d(u,t)\neq d(v,t)$, where $d(x,y)$ is the distance between vertices $x$ and $y$. The cardinality of a minimum resolving set for $G$ is called the metric dimension of $G$ and is denoted by $dim_{M}(G)$. This parameter has many applications in different areas. The problem of finding metric dimension is NP-complete for general graphs but it is determined for trees and some other important families of graphs. In this paper, we determine the exact value of the metric dimension of Andrásfai graphs, their complements and $And(k)\square P_n$. Also, we provide upper and lower bounds for $dim_M(And(k)\square C_n)$.
Access status: Open Access ,
The achromatic number of K6 □ K7 is 18
(Wydawnictwa AGH, 2021) Horňák, Mirko
A vertex colouring $f:V(G) \to C$ of a graph $G$ is complete if for any two distinct colours $c_{1},c_{2} \in C$ there is an edge $\{v1,v2\} \in E(G)$ such that $f(v_{i})=c_{i}$, $i=1,2$. The achromatic number of $G$ is the maximum number $\text{achr}(G)$ of colours in a proper complete vertex colouring of $G$. In the paper it is proved that $\text{achr}(K_6 \square K_7)=18$. This result finalises the determination of $\text{achr}(K_6 \square K_q)$.