zbMATH — the first resource for mathematics

Cordial labeling of hypertrees. (English) Zbl 1281.05118
Summary: Let \(H=(V,E)\) be a hypergraph with vertex set \(V=\{v_1,v_2,\dots ,v_n\}\) and edge set \(E=\{e_1,e_2,\dots ,e_m\}\). A vertex labeling \(c:V\to\mathbb N\) induces an edge labeling \(c^\ast :E\to\mathbb N\) by the rule \(c^\ast (e_i)=\sum_{v_j\in e_i}c(v_j)\). For integers \(k\geq 2\) we study the existence of labelings satisfying the following condition: every residue class modulo \(k\) occurs exactly \(\lfloor n/k\rfloor\) or \(\lceil n/k\rceil\) times in the sequence \(c(v_1),c(v_2),\dots ,c(v_n)\) and exactly \(\lfloor m/k\rfloor\) or \(\lceil m/k\rceil\) times in the sequence \(c^\ast (e_1),c^\ast (e_2),\dots ,c^\ast (e_m)\). Hypergraph \(H\) is called \(k\)-cordial if it admits a labeling with these properties.
M. Hovey [ibid. 93, No. 2–3, 183–194 (1991; Zbl 0753.05059)] 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 I. Cahit’s theorem [Ars Comb. 23, 201–207 (1987; Zbl 0616.05056)], which states that every tree graph is 2-cordial. We also prove that every uniform hyperpath is \(k\)-cordial for every \(k\).

05C78 Graph labelling (graceful graphs, bandwidth, etc.)
05C65 Hypergraphs
05C05 Trees
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
Full Text: DOI
[1] Cahit, I., Cordial graphs: a weaker version of graceful and harmonious graphs, Ars Combin., 23, 201-207, (1987) · Zbl 0616.05056
[2] Cairnie, N.; Edwards, K., The computational complexity of cordial and equitable labelling, Discrete Math., 216, 29-34, (2000) · Zbl 0951.05091
[3] Du, G. M., Cordiality of complete \(k\)-partite graphs and some special graphs, Neimenggu Shida Xuebao Ziran Kexue Hanwen Ban, 9-12, (1997)
[4] Gallian, J. A., A dynamic survey of graph labeling, Electron. J. Combin., 17, (2012), # DS6
[5] Hovey, M., \(A\)-cordial graphs, Discrete Math., 93, 183-194, (1991) · Zbl 0753.05059
[6] Lee, S. M.; Liu, A., A construction of cordial graphs from smaller cordial graphs, Ars Combin., 32, 209-214, (1991) · Zbl 0755.05086
[7] Seoud, M. A.; Maqsoud, A. E.I. A., On cordial and balanced labelings of graphs, J. Egyptian Math. Soc., 7, 127-135, (1999) · Zbl 0965.05086
[8] Youssef, M. Z., On \(k\)-cordial labelling, Australas. J. Combin., 43, 31-37, (2009) · Zbl 1170.05051
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.