TY - JOUR
AU - Omai, M. M.
AU - Campos, C. N.
AU - Luiz, A. G.
PY - 2021/07/18
TI - The (2,1)-total number of near-ladder graphs
JF - Anais do Encontro de Teoria da Computação (ETC); 2021: Anais do VI Encontro de Teoria da ComputaçãoDO - 10.5753/etc.2021.16390
KW -
N2 - A $(2,1)$-total labelling of a simple graph $G$ is a function $\pi \colon V(G)\cup E(G) \to \{0, \ldots, k\}$ such that: $\pi(u) \neq \pi(v)$ for $uv \in E(G)$; $\pi(uv) \neq \pi(vw)$ for $uv, vw \in E(G)$; and $|\pi(uv)-\pi(u)| \geq 2$ and $|\pi(uv)-\pi(v)| \geq 2$ for $uv \in E(G)$. The $(2,1)$-total number $\lambda_2^t(G)$ of $G$ is the least $k$ for which $G$ admits such a labelling. In 2008, Havet and Yu conjectured that $\lambda_2^t(G)\leq 5$ for every connected graph $G \not\cong K_4$ with $\Delta(G) \leq 3$. We prove that, for near-ladder graphs, $\lambda_2^t(G)=5$, verifying Havet and Yu's Conjecture for this class.
UR - https://sol.sbc.org.br/index.php/etc/article/view/16390