On the domination number of generalized Petersen graphs P(ck,k).

MaRDI QIDQ2804743zbMATH OpenFDO

Authors Haoli Wang, Xirong Xu, Yuansheng Yang, Guoqing Wang

Publication date 4 May 2016

Published in Ars Combinatoria (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1103.2427

zbMATH Keywords

domination numbergeneralized Petersen graph

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Connectivity (05C40)

Abstract: 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 $SsubseteqV(G)$ is a $dominating$ $set$ if for each $vinV(G)$ either $vinS$ or $v$ is adjacent to some $winS$. 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 $cgeq3$ and $kgeq3$. We also prove that $gamma(P(4k,k))=2k+1$ for even $k$, $gamma(P(5k,k))=3k$ for all $kgeq1$, and $gamma(P(6k,k))=lceilfrac10k3ceil$ for $kgeq1$ and $keq2$.

Recommendations

• Domination in the generalized Petersen graph \(P(ck,k)\)
• On the domination number of generalized Petersen graphs \(P(n,3)\).
• On the domination number of generalized petersen graphs \(P(n,2)\)
• The exact domination number of generalized Petersen graphs \(P(n,k)\) with \(n=2k\) and \(n=2k+2^\ast\)
• The exact domination number of the generalized Petersen graphs

Cited in

(17)

• The connected domination and tree domination of \(P(n,k)\) for \(k=1,2,\lfloor n/2\rfloor \).
• On rainbow domination of generalized Petersen graphs \(P ( c k , k )\)
• The exact domination number of generalized Petersen graphs \(P(n,k)\) with \(n=2k\) and \(n=2k+2^\ast\)
• On minimum vertex covers of generalized Petersen graphs
• On the independent domination number of the generalized Petersen graphs
• Domination in generalized Petersen graphs
• On the Roman domination numbers of generalized Petersen graphs
• On the domination number of generalized petersen graphs \(P(n,2)\)
• The exact domination number of the generalized Petersen graphs
• Vertex domination of generalized Petersen graphs
• Domination in the generalized Petersen graph \(P(ck,k)\)
• On the domination number of some graphs
• Domination in rose window graphs
• The connected and tree domination number of \(P(n,k)\) for \(k=4,6,8\)
• 2-domination number of generalized Petersen graphs
• On the domination number of the generalized Petersen graphs
• On the domination number of generalized Petersen graphs \(P(n,3)\).

This page was built for publication: On the domination number of generalized Petersen graphs \(P(ck,k)\).

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2804743)