Szczegóły publikacji
Opis bibliograficzny
Cordial labeling of hypertrees / Sylwia CICHACZ, Agnieszka GÖRLICH, Zsolt Tuza // Discrete Mathematics ; ISSN 0012-365X. — 2013 — vol. 313 iss. 22, s. 2518–2524. — Bibliogr. s. 2524, Abstr.
Autorzy (3)
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 76670 |
|---|---|
| Data dodania do BaDAP | 2013-10-14 |
| Tekst źródłowy | URL |
| DOI | 10.1016/j.disc.2013.07.025 |
| Rok publikacji | 2013 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | Discrete Mathematics |
Abstract
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(1)) = Sigma(vj is an element of ei) c(v(j)). For integers k >= 2 we study the existence of labelings satisfying the following condition: every residue class modulo k occurs exactly left perpendicularn/kright perpendicular or inverted right perpendicularn/kinverted left perpendicular times in the sequence c(v(1)), c(v(2)), ..., c(v(n)) and exactly left perpendicularm/kright perpendicular or inverted right perpendicularm/kinverted left perpendicular 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. Hovey [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. (C) 2013 Elsevier B.V. All rights reserved.
