Cordial labeling of hypertrees

Let H=(V,E)H=(V,E) be a hypergraph with vertex set V={v1,v2,…,vn}V={v1,v2,…,vn} and edge set E={e1,e2,…,em}E={e1,e2,…,em}. A vertex labeling c:V→Nc:V→N induces an edge labeling c∗:E→Nc∗:E→N by the rule c∗(ei)=∑vj∈eic(vj)c∗(ei)=∑vj∈eic(vj). For integers k≥2k≥2 we study the existence of labelings satisfying the following condition: every residue class modulo kk occurs exactly ⌊n/k⌋⌊n/k⌋ or ⌈n/k⌉⌈n/k⌉ times in the sequence c(v1),c(v2),…,c(vn)c(v1),c(v2),…,c(vn) and exactly ⌊m/k⌋⌊m/k⌋ or ⌈m/k⌉⌈m/k⌉ times in the sequence c∗(e1),c∗(e2),…,c∗(em)c∗(e1),c∗(e2),…,c∗(em). Hypergraph HH is called kk-cordial if it admits a labeling with these properties.Hovey [M. Hovey, A-cordial graphs, Discrete Math. 93 (1991) 183–194] raised the conjecture (still open for k>5k>5) that if HH is a tree graph, then it is kk-cordial for every kk. Here we investigate the analogous problem for hypertrees (connected hypergraphs without cycles) and present various sufficient conditions on HH to be kk-cordial. From our theorems it follows that every kk-uniform hypertree is kk-cordial, and every hypertree with nn or mm odd is 2-cordial. Both of these results generalize Cahit’s theorem [I. Cahit, Cordial graphs: a weaker version of graceful and harmonious graphs, Ars Combin. 23 (1987) 201–207] which states that every tree graph is 2-cordial. We also prove that every uniform hyperpath is kk-cordial for every kk.