Return to search

On the domination numbers of prisms of cycles

Let $gamma(G)$ be the domination number of a graph $G$. For any
permutation $pi$ of the vertex set of a graph $G$, the prism of $G$
with respect to $pi$ is the graph $pi G$ obtained from two copies
$G_{1}$ and $G_{2}$ of $G$ by joining $uin V(G_{1})$ and $vin
V(G_{2})$ iff $v=pi(u)$. We prove that
$$gamma(pi C_{n})geq cases{frac{ n}{ 2}, &if $n = 4k ,$ cr
leftlceilfrac{n+1}{2}
ight
ceil, &if $n
eq 4k$,} mbox{and }
gamma(pi C_{n}) leq leftlceil frac{2n-1}{3}
ight
ceil
mbox{for all }pi.$$ We also find a permutation $pi_{t}$ such that
$gamma(pi_{t} C_{n})=k$, where $k$ between the lower bound and the
upper bound of $gamma(pi C_{n})$ in above. Finally, we prove that
if $pi_{b}C_{n}$ is a bipartite graph, then
$$gamma(pi_{b}C_{n})geq cases{frac{n}{2}, &if $n = 4k ,$cr
leftlceilfrac{n+1}{2}
ight
ceil, &if $n = 4k+2$,} mbox{and }
gamma(pi_{b}C_{n})leq leftlfloor frac{5n+2}{8}
ight
floor.$$

Identiferoai:union.ndltd.org:NSYSU/oai:NSYSU:etd-0116108-155641
Date16 January 2008
CreatorsLin, Ming-Hung
Contributorsnone, Li-Da Tong, none
PublisherNSYSU
Source SetsNSYSU Electronic Thesis and Dissertation Archive
LanguageEnglish
Detected LanguageEnglish
Typetext
Formatapplication/pdf
Sourcehttp://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0116108-155641
Rightsunrestricted, Copyright information available at source archive

Page generated in 0.002 seconds