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

On k-domination and j-dependence in graphs

Presented by Dr. Adriana HANSBERG
Type: Oral presentation
Track: Coloring, independence and forbidden subgraphs


Let $G$ be a graph and let $k$ and $j$ be positive integers. A subset $D$ of the vertex set of $G$ is a {\it $k$-dominating set} if every vertex not in $D$ has at least $k$ neighbors in $D$. The {\it $k$-domination number} $\gamma_k(G)$ is the minimum cardinality among the $k$-dominating sets of $G$. A subset $I \subseteq V(G)$ is a {\it $j$-dependent set} of $G$ if every vertex in $I$ has at most $j-1$ neighbors in $I$. The {\it $j$-dependence number} $\alpha_j(G)$ is the maximum cardinality among all $j$-dependent sets of $G$. In this work, we study the interaction between $\gamma_k(G)$ and $\alpha_j(G)$ in a graph $G$. Hereby, we generalize some known inequalities concerning these parameters and put into relation different known and new bounds on $k$-domination and $j$-dependence that turn to be symmetrical in a certain manner. Finally, we will discuss several consequences that follow from the given relations.


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

Primary authors