On cordial labeling of hypertrees

zbMATH Open1430.05105arXiv1711.06294MaRDI QIDQ5207840FDOQ5207840

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

Publication date: 13 January 2020

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.

Full work available at URL: https://arxiv.org/abs/1711.06294

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

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)

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
• Title not available (Why is that?)
• 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)