1. Domination in Knödel Graphs
- Author
-
Racicot, Jesse and Rosso, Giovanni
- Subjects
FOS: Mathematics ,Combinatorics (math.CO) - Abstract
Given a graph and an integer $k$, it is an NP-complete problem to decide whether there is a dominating set of size at most $k$. In this paper we study this problem for the Knödel Graph on $n$ vertices using elementary number theory techniques. In particular, we show an explicit upper bound for the domination number of the Knödel Graph on $n$ vertices any time that we can find a prime number $p$ dividing $n$ for which $2$ is a primitive root., Comments welcome!
- Published
- 2021
- Full Text
- View/download PDF