Date of Award

5-2014

Document Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Legacy Department

Mathematical Science

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.

Included in

Mathematics Commons

Share

COinS