Dominating sets in finite generalized quadrangles
Abstract
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.
Keywords
DOI: https://doi.org/10.26493/1855-3974.2106.423
ISSN: 1855-3974
Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications