Geodesic
ℤ2 × ℤ2 -Cordial Cycle-Free Hypergraphs
Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 4, pp. 1021-1040 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

Hovey introduced A-cordial labelings as a generalization of cordial and harmonious labelings [7]. If A is an Abelian group, then a labeling f : V (G) → A of the vertices of some graph G induces an edge labeling on G; the edge uv receives the label f(u) + f(v). A graph G is A-cordial if there is a vertex-labeling such that (1) the vertex label classes differ in size by at most one and (2) the induced edge label classes differ in size by at most one. The problem of A-cordial labelings of graphs can be naturally extended for hypergraphs. It was shown that not every 2-uniform hypertree (i.e., tree) admits a ℤ2 × ℤ2-cordial labeling [8]. The situation changes if we consider p-uniform hypertrees for a bigger p. We prove that a p-uniform hypertree is ℤ2 × ℤ2-cordial for any p gt; 2, and so is every path hypergraph in which all edges have size at least 3. The property is not valid universally in the class of hypergraphs of maximum degree 1, for which we provide a necessary and sufficient condition.
Keywords: V 4 -cordial graph, hypergraph, labeling of hypergraph, hyper-tree 
@article{DMGT_2021_41_4_a9,
     author = {Cichacz, Sylwia and G\"orlich, Agnieszka and Tuza, Zsolt},
     title = {\ensuremath{\mathbb{Z}}\protect\textsubscript{2} {\texttimes} {\ensuremath{\mathbb{Z}}\protect\textsubscript{2}} {-Cordial} {Cycle-Free} {Hypergraphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1021--1040},
     year = {2021},
     volume = {41},
     number = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2021_41_4_a9/}
}
TY  - JOUR
AU  - Cichacz, Sylwia
AU  - Görlich, Agnieszka
AU  - Tuza, Zsolt
TI  - ℤ2 × ℤ2 -Cordial Cycle-Free Hypergraphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2021
SP  - 1021
EP  - 1040
VL  - 41
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DMGT_2021_41_4_a9/
LA  - en
ID  - DMGT_2021_41_4_a9
ER  - 
%0 Journal Article
%A Cichacz, Sylwia
%A Görlich, Agnieszka
%A Tuza, Zsolt
%T ℤ2 × ℤ2 -Cordial Cycle-Free Hypergraphs
%J Discussiones Mathematicae. Graph Theory
%D 2021
%P 1021-1040
%V 41
%N 4
%U http://geodesic.mathdoc.fr/item/DMGT_2021_41_4_a9/
%G en
%F DMGT_2021_41_4_a9
Cichacz, Sylwia; Görlich, Agnieszka; Tuza, Zsolt. ℤ2 × ℤ2 -Cordial Cycle-Free Hypergraphs. Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 4, pp. 1021-1040. http://geodesic.mathdoc.fr/item/DMGT_2021_41_4_a9/

[1] I. Cahit, Cordial graphs: a weaker version of graceful and harmonious graphs, Ars Combin. 23 (1987) 201–207.

[2] N. Cairnie and K. Edwards, The computational complexity of cordial and equitable labelling, Discrete Math. 216 (2000) 29–34. https://doi.org/10.1016/S0012-365X(99)00295-2

[3] S. Cichacz, A. Görlich and Zs. Tuza, Cordial labeling of hypertrees, Discrete Math. 313 (2013) 2518–2524. https://doi.org/10.1016/j.disc.2013.07.025

[4] K. Driscoll, E. Krop and M. Nguyen, All trees are six-cordial, Electron. J. Graph Theory Appl. 5 (2017) 21–35. https://doi.org/10.5614/ejgta.2017.5.1.3

[5] J.A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin. 17 (2010) #DS6.

[6] I.M. Gessel and L.H. Kalikow, Hypergraphs and a functional equation of Bouwkamp and De Bruijn, J. Comb. Theory Ser. A 110 (2005) 275–289. https://doi.org/10.1016/j.jcta.2004.11.002

[7] M. Hovey, A-cordial graphs, Discrete Math. 93 (1991) 183–194. https://doi.org/10.1016/0012-365X(91)90254-Y

[8] O. Pechenik and J. Wise, Generalized graph cordiality, Discuss. Math. Graph Theory 32 (2012) 557–567. https://doi.org/10.7151/dmgt.1626

[9] M. Tuczyński, P. Wenus and K. Węsek, On cordial hypertrees (2017). arXiv:1711.06294