Item request has been placed! ×
Item request cannot be made. ×
loading  Processing Request

Domination in Kn\'odel Graphs

Item request has been placed! ×
Item request cannot be made. ×
loading   Processing Request
  • Additional Information
    • Publication Date:
      2021
    • Collection:
      Mathematics
    • 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\"odel Graph on $n$ vertices using elementary number theory techniques. In particular, we show an explicit upper bound for the domination number of the Kn\"odel Graph on $n$ vertices any time that we can find a prime number $p$ dividing $n$ for which $2$ is a primitive root.
      Comment: Comments welcome!
    • Accession Number:
      10.46298/dmtcs.7158
    • Accession Number:
      edsarx.2102.00505