Abstract
dc:description.abstractAn 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 Kn \times Km. In particular, we answer a question of Klav\v{z}ar and show the exact value of \gid(Kn \times Km). It was recently shown by Gravier, Moncel and Semri that for the Cartesian product of two same-sized cliques \gid(Kn \Box Kn) = \lfloor{\frac{3n}{2}\rfloor}. Letting $m \ge n \ge 2$ be any integers, we show that \IDCODE(Kn \cartprod Km) = \max\{2m-n, m + \lfloor n/2 \rfloor\}. Furthermore, we improve upon the bounds for \IDCODE(G \cartprod Km) and explore the specific case when $G$ is the Cartesian product of multiple cliques. Given two disjoint copies of a graph $G$, denoted G1 and G2, and a permutation π of $V(G)$, the permutation graph π G is constructed by joining u \in V(G1) to π(u) \in V(G2) for all u \in V(G1). The graph $G$ is said to be a universal fixer if the domination number of π G is equal to the domination number of $G$ for all π of $V(G)$. In 1999 it was conjectured that the only universal fixers are the edgeless graphs. We prove the conjecture.
Degree
thesis:*- Name thesis:degree_name
- Doctor of Philosophy (PhD)
- Level thesis:degree_level
- Dissertation
- Discipline thesis:degree_discipline
- Mathematical Science
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Wash, Kirsti
- Contributors dc:contributor
-
- Goddard, Wayne
- Rall, Douglas
- Hedetniemi, Stephen
- Brown, James
- Matthews, Gretchen
Subjects
dc:subject × 6Identifiers
dc:identifier.*- Repository record dc:identifier
- https://open.clemson.edu/all_dissertations/1356