2022/11/25 by Spiro, Sam, Adriaensen, Sam, Mattheus, Sam
#05B05 #05C70 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2211.14339
A set of edges Γ of a graph G is an edge dominating set if every edge of G intersects at least one edge of Γ, and the edge domination number γe(G) is the smallest size of an edge dominating set. Expanding on work of Laskar and Wallis, we study γe(G) for graphs G which are the incidence graph of some incidence structure D, with an emphasis on the case when D is a symmetric design. In particular, we show in this latter case that determining γe(G) is equivalent to determining the largest size of certain incidence-free sets of D. Throughout, we employ a variety of combinatorial, probabilistic and geometric techniques, supplemented with tools from spectral graph theory.