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.0023 seconds