2013/08/14 by Samuel Connolly, Connolly, Samuel, Zachary Gabor +5
Computer Science · Mathematics · #05C69 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.1308.3210
openalex publication_date 2013/08/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We use probabilistic methods to find lower bounds on the maximum number, in a graph with domination number γ, of dominating sets of size γ. We find that we can randomly generate a graph that, w.h.p., is dominated by almost all sets of size γ. At the same time, we use a modified adjacency matrix to obtain lower bounds on the number of sets of a given size that do not dominate a graph on n vertices