Let $G\ensuremath{\mathbin{\raisebox{0.3mm}{$\scriptstyle\square$}}} H$ denote the Cartesian product of the graphs $G$ and $H$. Domination of the Cartesian product of two graphs has received much attention, with a main objective to confirm the truth of Vizing's well-known conjecture. The conjecture states that the domination number of the Cartesian product of two graphs is at least as large as the product of the respective domination numbers. The potential truth of Vizing's conjecture gives rise to investigating the domination of graph products that generalizes the Cartesian product. The generalized prism $\pi G$ of $G$ is the graph consisting of two copies of $G$, with edges between the copies determined by a permutation $\pi$ acting on the vertices of $G$. A generalized Cartesian product $G\ensuremath{\mathbin{\raisebox{0.3mm}{${\scriptstyle \square}$}\hspace{-1.99mm}\raisebox{0.65mm}{${\scriptstyle \pi}$}}} H$ is defined here, incorporating structural properties of both the Cartesian product of two graphs as well as the generalized prism of a graph.
Conditions on the isomorphism of two generalized Cartesian products are explored first, establishing a characterization in the case of natural isomorphisms. A comparison of the diameter of the generalized Cartesian product and the corresponding Cartesian product graph is used to illustrate the structural differences between these graph products. This comparison is continued through a study of the validity of an inequality similar to Vizing's conjecture for Cartesian products.
Graphs that attain equality in the general bounds for the domination number of the Cartesian product and generalized Cartesian product are investigated in more detail. For any graph $G$ and $n\geq 2$, $\min\{|V(G)|,\gamma(G)+n-2\}\leq\gamma(G\ensuremath{\mathbin{\raisebox{0.3mm}{$\scriptstyle\square$}}} K_{n})\leq n\gamma(G)$. A graph $G$ is called a consistent Cartesian fixer if $\gamma(G\ensuremath{\mathbin{\raisebox{0.3mm}{$\scriptstyle\square$}}} K_{n})=\gamma(G)+n-2$ for each $n$ such that $2\leq n<|V(G)|-\gamma(G)+2$. A graph attaining equality in the stated upper bound on $\gamma(G\ensuremath{\mathbin{\raisebox{0.3mm}{$\scriptstyle\square$}}} K_{n})$ is called a Cartesian $n$-multiplier. Both of these classes are characterized. Concerning the generalized Cartesian product, $\gamma(G\ensuremath{\mathbin{\raisebox{0.3mm}{${\scriptstyle \square}$}\hspace{-1.99mm}\raisebox{0.65mm}{${\scriptstyle \pi}$}}} K_{n})\leq n\gamma(G)$ for any graph $G$, permutation $\pi$ and $n\geq 2$. A graph attaining equality in the upper bound for all $\pi$ is called a universal multiplier. Such graphs are characterized similar to a known result for generalized prisms. A similar problem for the product $G\ensuremath{\mathbin{\raisebox{0.3mm}{${\scriptstyle \square}$}\hspace{-1.99mm}\raisebox{0.65mm}{${\scriptstyle \pi}$}}} C_{n}$ is considered, with conditions on a graph being a so-called cycle multiplier provided. A graph attaining equality in the lower bound $\gamma(G\ensuremath{\mathbin{\raisebox{0.3mm}{${\scriptstyle \square}$}\hspace{-1.99mm}\raisebox{0.65mm}{${\scriptstyle \pi}$}}} H)\geq\gamma(G)$ for some permutation $\pi$ is called a $\pi$-$H$-fixer. A brief investigation is conducted into the existence of universal $H$-fixers, i.e.~graphs that are $\pi$-$H$-fixers for some $H$ and all permuations $\pi$ of $V(G)$, and it is shown that no such graphs exist when $n\geq 3$.
A known efficient algorithm for determining $\gamma(G\ensuremath{\mathbin{\raisebox{0.3mm}{$\scriptstyle\square$}}} P_{n})$ is surveyed, and modified to accommodate any Cartesian product $G\ensuremath{\mathbin{\raisebox{0.3mm}{$\scriptstyle\square$}}} H$, thereby establishing a general framework for evaluating the domination number of $G\ensuremath{\mathbin{\raisebox{0.3mm}{$\scriptstyle\square$}}} H$ for a fixed graph $G$ and any $H$. An algorithm to determine $\gamma(G\ensuremath{\mathbin{\raisebox{0.3mm}{$\scriptstyle\square$}}} T)$ for any tree $T$ is provided, and it is observed to be polynomial for trees of bounded maximum degree. The general framework for $G\ensuremath{\mathbin{\raisebox{0.3mm}{$\scriptstyle\square$}}} H$ is also modified to accommodate the generalized Cartesian product $G\ensuremath{\mathbin{\raisebox{0.3mm}{${\scriptstyle \square}$}\hspace{-1.99mm}\raisebox{0.65mm}{${\scriptstyle \pi}$}}} H$.
The study diverts from the main topic of domination to investigate the planarity of the generalized Cartesian product graph. If both $G$ and $H$ are 2-connected graphs, then $G\ensuremath{\mathbin{\raisebox{0.3mm}{${\scriptstyle \square}$}\hspace{-1.99mm}\raisebox{0.65mm}{${\scriptstyle \pi}$}}} H$ is nonplanar. A known simple polynomial-time planarity testing algorithm is surveyed, and used to establish conditions on the planarity of $P_{m}\ensuremath{\mathbin{\raisebox{0.3mm}{${\scriptstyle \square}$}\hspace{-1.99mm}\raisebox{0.65mm}{${\scriptstyle \pi}$}}} P_{n}$, the generalized Cartesian product of two paths.
This research aims to lay the foundation on which further properties of the generalized Cartesian product and further generalizations may be studied, as well as to provide various open problems to spark interest in the research area.
| Identifer | oai:union.ndltd.org:uvic.ca/oai:dspace.library.uvic.ca:1828/1493 |
| Date | 12 August 2009 |
| Creators | Benecke, Stephen |
| Contributors | Mynhardt, C. M. |
| Source Sets | University of Victoria |
| Language | English, English |
| Detected Language | English |
| Type | Thesis |
| Rights | Available to the World Wide Web |
Page generated in 0.002 seconds