Back to search

Clemson University

Identifying Codes and Domination in the Product of Graphs

Abstract

dc:description.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 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 × 6

Identifiers

dc:identifier.*
Repository record dc:identifier
https://open.clemson.edu/all_dissertations/1356

Chain of custody

source
Harvested from
Clemson University
Base URL
open.clemson.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Wash, Kirsti. Identifying Codes and Domination in the Product of Graphs. Dissertation thesis, https://open.clemson.edu/all_dissertations/1356