Partitioning a graph into defensive k-alliances

Details Partitioning a graph into defensive k-alliances Partitioning a graph into defensive k-alliances

2009-01-30

arxiv.org/abs/0901.4923v2

Mathematics

Combinatorics

Scientific paper

10.1007/s10114-010-9075-6

A defensive $k$-alliance in a graph is a set $S$ of vertices with the property that every vertex in $S$ has at least $k$ more neighbors in $S$ than it has outside of $S$. A defensive $k$-alliance $S$ is called global if it forms a dominating set. In this paper we study the problem of partitioning the vertex set of a graph into (global) defensive $k$-alliances. The (global) defensive $k$-alliance partition number of a graph $\Gamma=(V,E)$, ($\psi_{k}^{gd}(\Gamma)$) $\psi_k^{d}(\Gamma)$, is defined to be the maximum number of sets in a partition of $V$ such that each set is a (global) defensive $k$-alliance. We obtain tight bounds on $\psi_k^{d}(\Gamma)$ and $\psi_{k}^{gd}(\Gamma)$ in terms of several parameters of the graph including the order, size, maximum and minimum degree, the algebraic connectivity and the isoperimetric number. Moreover, we study the close relationships that exist among partitions of $\Gamma_1\times \Gamma_2$ into (global) defensive $(k_1+k_2)$-alliances and partitions of $\Gamma_i$ into (global) defensive $k_i$-alliances, $i\in \{1,2\}$.

Affiliated with

Also associated with

No associations

Rating

Partitioning a graph into defensive k-alliances 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 Partitioning a graph into defensive k-alliances, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Partitioning a graph into defensive k-alliances will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-425223