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

dmtcs:4081 - Discrete Mathematics & Theoretical Computer Science, August 7, 2019, vol. 21 no. 4 - https://doi.org/10.23638/DMTCS-21-4-1
On cordial labeling of hypertreesArticle

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

    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.


    Volume: vol. 21 no. 4
    Section: Graph Theory
    Published on: August 7, 2019
    Accepted on: June 20, 2019
    Submitted on: November 21, 2017
    Keywords: Mathematics - Combinatorics,05C15 (Primary), 05C65 (Secondary)

    Consultation statistics

    This page has been seen 1228 times.
    This article's PDF has been downloaded 441 times.