On the Domination Number of Generalized Petersen Graphs P(ck,k)

Details On the Domination Number of Generalized Petersen Graphs P(ck,k) On the Domination Number of Generalized Petersen Graphs P(ck,k)

2011-03-12

arxiv.org/abs/1103.2427v1

Mathematics

Combinatorics

13 pages

Scientific paper

Let $G=(V(G),E(G))$ be a simple connected and undirected graph with vertex set $V(G)$ and edge set $E(G)$. A set $S \subseteq V(G)$ is a $dominating$ $set$ if for each $v \in V(G)$ either $v \in S$ or $v$ is adjacent to some $w \in S$. That is, $S$ is a dominating set if and only if $N[S]=V(G)$. The domination number $\gamma(G)$ is the minimum cardinalities of minimal dominating sets. In this paper, we give an improved upper bound on the domination number of generalized Petersen graphs $P(ck,k)$ for $c\geq 3$ and $k\geq 3$. We also prove that $\gamma(P(4k,k))=2k+1$ for even $k$, $\gamma(P(5k,k))=3k$ for all $k\geq 1$, and $\gamma(P(6k,k))=\lceil\frac{10k}{3}\rceil$ for $k\geq 1$ and $k\neq 2$.

Affiliated with

Also associated with

No associations

Rating

On the Domination Number of Generalized Petersen Graphs P(ck,k) 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 On the Domination Number of Generalized Petersen Graphs P(ck,k), we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Domination Number of Generalized Petersen Graphs P(ck,k) will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-278817