Tuczyński, Michał and Wenus, Przemysław and Węsek, Krzysztof - On cordial labeling of hypertrees

dmtcs:4081 - Discrete Mathematics & Theoretical Computer Science, August 7, 2019, vol. 21 no. 4
On cordial labeling of hypertrees

Authors: Tuczyński, Michał and Wenus, Przemysław and Węsek, Krzysztof

Let $f:V\rightarrow\mathbb{Z}_k$ be a vertex labeling of a hypergraph $H=(V,E)$. This labeling induces an~edge labeling of $H$ defined by $f(e)=\sum_{v\in e}f(v)$, where the sum is taken modulo $k$. We say that $f$ is $k$-cordial if for all $a, b \in \mathbb{Z}_k$ the number of vertices with label $a$ differs by at most $1$ from the number of vertices with label $b$ and the analogous condition holds also for labels of edges. If $H$ admits a $k$-cordial labeling then $H$ is called $k$-cordial. The existence of $k$-cordial labelings has been investigated for graphs for decades. Hovey~(1991) conjectured that every tree $T$ is $k$-cordial for every $k\ge 2$. Cichacz, Görlich and Tuza~(2013) were first to investigate the analogous problem for hypertrees, that is, connected hypergraphs without cycles. The main results of their work are that every $k$-uniform hypertree is $k$-cordial for every $k\ge 2$ and that every hypertree with $n$ or $m$ odd is $2$-cordial. Moreover, they conjectured that in fact all hypertrees are $2$-cordial. In this article, we confirm the conjecture of Cichacz et al. and make a step further by proving that for $k\in\{2,3\}$ every hypertree is $k$-cordial.


Source : oai:arXiv.org:1711.06294
Volume: vol. 21 no. 4
Section: Graph Theory
Published on: August 7, 2019
Submitted on: November 21, 2017
Keywords: Mathematics - Combinatorics,05C15 (Primary), 05C65 (Secondary)


Share