Dominating sets in finite generalized quadrangles
DOI:
https://doi.org/10.26493/1855-3974.2106.423Keywords:
Dominating set, finite generalized quadrangleAbstract
A dominating set in a graph is a set of vertices such that each vertex not in the set has a neighbor in the set. The domination number is the smallest size of a dominating set. We consider this problem in the incidence graph of a generalized quadrangle. We show that the domination number of a generalized quadrangle with parameters s and t is at most 2st + 1, and we prove that this bound is sharp if s = t or if s = q − 1 and t = q + 1. Moreover, we give a complete classification of smallest dominating sets in generalized quadrangles where s = t, and give some general results for small dominating sets in the general case.
Downloads
Published
Issue
Section
License
Articles in this journal are published under Creative Commons Attribution 4.0 International License
https://creativecommons.org/licenses/by/4.0/