Date of Award
5-2014
Document Type
Dissertation
Degree Name
Doctor of Philosophy (PhD)
Legacy Department
Mathematical Science
Committee Chair/Advisor
Goddard, Wayne
Committee Member
Rall, Douglas
Committee Member
Hedetniemi, Stephen
Committee Member
Brown, James
Committee Member
Matthews, Gretchen
Abstract
An identifying code in a graph is a dominating set that also has the property that the closed neighborhood of each vertex in the graph has a distinct intersection with the set. The minimum cardinality of an identifying code in a graph $G$ is denoted $\gid(G)$. We consider identifying codes of the direct product $K_n \times K_m$. In particular, we answer a question of Klav\v{z}ar and show the exact value of $\gid(K_n \times K_m)$. It was recently shown by Gravier, Moncel and Semri that for the Cartesian product of two same-sized cliques $\gid(K_n \Box K_n) = \lfloor{\frac{3n}{2}\rfloor}$. Letting $m \ge n \ge 2$ be any integers, we show that $\IDCODE(K_n \cartprod K_m) = \max\{2m-n, m + \lfloor n/2 \rfloor\}$. Furthermore, we improve upon the bounds for $\IDCODE(G \cartprod K_m)$ and explore the specific case when $G$ is the Cartesian product of multiple cliques. Given two disjoint copies of a graph $G$, denoted $G^1$ and $G^2$, and a permutation $\pi$ of $V(G)$, the permutation graph $\pi G$ is constructed by joining $u \in V(G^1)$ to $\pi(u) \in V(G^2)$ for all $u \in V(G^1)$. The graph $G$ is said to be a universal fixer if the domination number of $\pi G$ is equal to the domination number of $G$ for all $\pi$ of $V(G)$. In 1999 it was conjectured that the only universal fixers are the edgeless graphs. We prove the conjecture.
Recommended Citation
Wash, Kirsti, "Identifying Codes and Domination in the Product of Graphs" (2014). All Dissertations. 1356.
https://tigerprints.clemson.edu/all_dissertations/1356