Cycle Domination, Independence and Irredundance in graphs

Abstract

A set $S$ of vertices in a graph $G=(V,E)$ is called {\em cycle independent} if the induced subgraph $⟨S⟩$ is acyclic, and called {\em odd-cycle indepdendet} if $⟨S⟩$ is bipartite. A set $S$ is {\em cycle dominating} (resp. {\em odd-cycle dominating}) if for every vertex $u\in V\setminus S$ there exists a vertex $v\in S$ such that $u$ and $v$ are contained in a (resp. odd cycle) cycle in $⟨S\setminus \{u\}⟩$. A set $S$ is {\em cycle irredundant} (resp. odd-cycle irredundant) if for every vertex $v\in S$ there exists a vertex $u\in V\setminus S$ such that $u$ and $v$ are in a (resp. odd cycle) cycle of $⟨S\setminus \{u\}⟩$, but $u$ is not in a cycle of $⟨S\cup \{u\}\setminus \{v\}⟩$. In this paper we present these new concepts, which relate in a natural way to independence, domination and irredundance in graphs. In particular, we construct analogs to the domination inequality chain for these new concepts.