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

zbMATH Open1349.05265arXiv1103.2427MaRDI QIDQ2804743FDOQ2804743

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

Publication date: 4 May 2016

Published in: Ars Combinatoria (Search for Journal in Brave)

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$.

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

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

zbMATH Keywords

domination numbergeneralized Petersen graph

Mathematics Subject Classification ID

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

Cited In (16)

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

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)