DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


Authors:

S. Cichacz, A. Görlich, Zs. Tuza

Title:

$\mathbb{Z}_2\times\mathbb{Z}_2$-cordial cycle-free hypergraphs

Source:

Discussiones Mathematicae Graph Theory

Received: 2018-09-01, Revised: 2019-04-05, Accepted: 2019-04-05, https://doi.org/10.7151/dmgt.2226

Abstract:

Hovey introduced $A$-cordial labelings as a generalization of cordial and harmonious labelings \cite{Hovey}. If $A$ is an Abelian group, then a labeling $f \colon V (G) \rightarrow 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.<br>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 $\mathbb{Z}_2\times\mathbb{Z}_2$-cordial labeling \cite{Pechnik}. The situation changes if we consider $p$-uniform hypertrees for a bigger $p$. We prove that a $p$-uniform hypertree is $\mathbb{Z}_2\times\mathbb{Z}_2$-cordial for any $p>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, hypertree

PDF
Close