On cordial labeling of hypertrees

MaRDI QIDQ5207840zbMATH OpenFDO

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

Publication date 13 January 2020

Full work available at URL https://arxiv.org/abs/1711.06294, https://dmtcs.episciences.org/5658/pdf

zbMATH Keywords

hypergraphhypertree\(k\)-cordial graphhypergraph labeling

Mathematics Subject Classification ID

Trees (05C05) Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Abstract: Let $f:Vightarrowmathbb{Z}_k$ be a vertex labeling of a hypergraph $H=(V,E)$. This labeling induces an~edge labeling of $H$ defined by $f(e)=su{m}_{vine}f(v)$, where the sum is taken modulo $k$. We say that $f$ is $k$-cordial if for all $a,binmathbb{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 $kge2$. Cichacz, G"orlich 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 $kge2$ 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 $kin2,3$ every hypertree is $k$-cordial.

Recommendations

• Cordial labeling of hypertrees
• scientific article; zbMATH DE number 844143
• scientific article; zbMATH DE number 94970
• The \(H_k\)-cordiality of trees
• On γ-labelings of trees
• On Graceful Labelings of Trees
• The L(2,1)-labelling of trees
• The relationships among several labelings of trees
• The \(L(h,1,1)\)-labelling problem for trees
• scientific article; zbMATH DE number 7528092

Cited in

(8)

• Cordial labeling of hypertrees
• All trees are six-cordial
• (2, 3)-cordial oriented hypercubes
• \( \mathbb{Z}_2 \times \mathbb{Z}_2\)-cordial cycle-free hypergraphs
• scientific article; zbMATH DE number 844143 (Why is no real title available?)
• A Partial Solution to Cordial Tree Conjecture
• The \(H_k\)-cordiality of trees
• Klein cordial trees and odd cyclic cordial friendship graphs

This page was built for publication: On cordial labeling of hypertrees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5207840)