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.$$
Identifer | oai:union.ndltd.org:NSYSU/oai:NSYSU:etd-0116108-155641 |
Date | 16 January 2008 |
Creators | Lin, Ming-Hung |
Contributors | none, Li-Da Tong, none |
Publisher | NSYSU |
Source Sets | NSYSU Electronic Thesis and Dissertation Archive |
Language | English |
Detected Language | English |
Type | text |
Format | application/pdf |
Source | http://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0116108-155641 |
Rights | unrestricted, Copyright information available at source archive |
Page generated in 0.0021 seconds