A dominating set of a graph $G$ is a subset of $V(G)$ with the property, that every vertex of graph $G$ is either in this set or is adjacent to the vertex in it. The domination number $\gamma(G)$ of a graph $G$ is the cardinality of a smallest dominating set. In this thesis we find the exact value of the domination number of the strong product of a complete graph with a path. It is not dependent on the order of the complete graph and is equal to $\gamma(K_m \boxtimes P_n) = \lceil \frac{n}{3} \rceil$. A bondage edge set of a graph $G$ is a subset of $E(G)$, whose removal from $G$ results in a graph with the domination number greater than that of $G$. The bondage number $b(G)$ is the cardinality of a smallest bondage edge set. It is a parameter to measure the vulnerability of a communication network under link failure. The bondage number of the strong product of a complete graph with a path depends on the order of the complete graph and the value of $n \pmod{3}$. For integers $m$ and $n$, where $m\geq 1$ and $n \geq 2$, $b(K_m \boxtimes P_n)=\lceil \frac{m}{2} \rceil$ if $n\equiv 0 \pmod{3}$, $b(K_m \boxtimes P_n)=\lceil \frac{3m}{2} \rceil$ if $n\equiv 1 \pmod{3}$ and $b(K_m \boxtimes P_n)=m$ if $n\equiv 2 \pmod{3}$.
|
