Jesse Racicot ; Giovanni Rosso - Domination in Knödel Graphs

dmtcs:7158 - Discrete Mathematics & Theoretical Computer Science, May 6, 2022, vol. 24, no. 1 -
Domination in Knödel Graphs

Authors: Jesse Racicot ; Giovanni Rosso

    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.

    Volume: vol. 24, no. 1
    Section: Graph Theory
    Published on: May 6, 2022
    Accepted on: March 30, 2022
    Submitted on: February 5, 2021
    Keywords: Mathematics - Combinatorics


    Consultation statistics

    This page has been seen 441 times.
    This article's PDF has been downloaded 469 times.