Alliance free sets in Cartesian product graphs

Details Alliance free sets in Cartesian product graphs Alliance free sets in Cartesian product graphs

2011-12-09

arxiv.org/abs/1112.2068v1

Mathematics

Combinatorics

Scientific paper

Let $G=(V,E)$ be a graph. For a non-empty subset of vertices $S\subseteq V$, and vertex $v\in V$, let $\delta_S(v)=|\{u\in S:uv\in E\}|$ denote the cardinality of the set of neighbors of $v$ in $S$, and let $\bar{S}=V-S$. Consider the following condition: {equation}\label{alliancecondition} \delta_S(v)\ge \delta_{\bar{S}}(v)+k, \{equation} which states that a vertex $v$ has at least $k$ more neighbors in $S$ than it has in $\bar{S}$. A set $S\subseteq V$ that satisfies Condition (\ref{alliancecondition}) for every vertex $v \in S$ is called a \emph{defensive} $k$-\emph{alliance}; for every vertex $v$ in the neighborhood of $S$ is called an \emph{offensive} $k$-\emph{alliance}. A subset of vertices $S\subseteq V$, is a \emph{powerful} $k$-\emph{alliance} if it is both a defensive $k$-alliance and an offensive $(k +2)$-alliance. Moreover, a subset $X\subset V$ is a defensive (an offensive or a powerful) $k$-alliance free set if $X$ does not contain any defensive (offensive or powerful, respectively) $k$-alliance. In this article we study the relationships between defensive (offensive, powerful) $k$-alliance free sets in Cartesian product graphs and defensive (offensive, powerful) $k$-alliance free sets in the factor graphs.

Affiliated with

Also associated with

No associations

Rating

Alliance free sets in Cartesian product graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Alliance free sets in Cartesian product graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Alliance free sets in Cartesian product graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-43771