Cordial labeling of hypertrees

Let H = ( V , E ) be a hypergraph with vertex set V = { v 1 , v 2 , … , v n } and edge set E = { e 1 , e 2 , … , e m } . A vertex labeling c : V → N induces an edge labeling c ∗ : E → N by the rule c ∗ ( e i ) = ∑ v j ∈ e i c ( v j ) . For integers k ≥ 2 we study the existence of labelings satisfying the following condition: every residue class modulo k occurs exactly ⌊ n / k ⌋ or ⌈ n / k ⌉ times in the sequence c ( v 1 ) , c ( v 2 ) , … , c ( v n ) and exactly ⌊ m / k ⌋ or ⌈ m / k ⌉ times in the sequence c ∗ ( e 1 ) , c ∗ ( e 2 ) , … , c ∗ ( e m ) . Hypergraph H is called k -cordial if it admits a labeling with these properties. [M. Hovey, A-cordial graphs, Discrete Math. 93 (1991) 183–194] raised the conjecture (still open for k > 5 ) that if H is a tree graph, then it is k -cordial for every k . Here we investigate the analogous problem for hypertrees (connected hypergraphs without cycles) and present various sufficient conditions on H to be k -cordial. From our theorems it follows that every k -uniform hypertree is k -cordial, and every hypertree with n or m 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 k -cordial for every k .