19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Home > Timetable > Contribution details

Domatic parameters and hypergraphs

Presented by Dr. Dirk MEIERLING
Type: Oral presentation
Track: General session


Let $H$ be a hypergraph with finite vertex set $X$ and finite hyperedge set $E$ and $Y\subset\mathbb{R}$ a subset of the real numbers. A $Y$-valued function $f\colon X\to Y$ with the property that for any hyperedge $e\in E$, the condition $f(e)=\sum_{x\in e} f(x)\ge 1$ is fulfilled is called a \emph{$Y$-transversal function} of $H$. The set $Y$ is called \emph{weight set} and the \emph{weight} of a $Y$-transversal function~$f$ is the value $\omega(f)=\sum_{x\in X} f(x)$. A family $\{f_1,f_2,\ldots,f_d\}$ of distinct $Y$-transversal functions of $H$ with the property that $\sum_{i=1}^d f_i(x)\le 1$ for each $x\in X$, is called a \emph{$Y$-partition} on~$H$. The maximum number of functions in such a family is the \emph{$Y$-partition number} of $H$, denoted by $d_{Y}(H)$. We present basic properties and bounds for the $Y$-partition number of a hypergraph. In addition, we determine the $Y$-partition number of some classes of hypergraphs. Various domination parameters of graphs as well as the related domatic parameters may be described in terms of $Y$-transversal functions by choosing an appropriate weight set~$Y$ and associated hypergraph~$H$ (for example the neighborhood hypergraph of $G$). Hence, some of our results are generalizations of well-known properties of various domatic parameters of graphs and directed graphs.


Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled

Primary authors