2015/12/20 by Yinglei Song, Song, Yinglei
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Interconnection Networks and Systems #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1512.06338
openalex publication_date 2015/12/20 · arxiv created 2016/01/04 · arxiv updated 2016/01/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we obtain lower bounds for the domination numbers of connected graphs with girth at least 7. We show that the domination number of a connected graph with girth at least 7 is either 1 or at least (1)/(2)(3+√(8(m-n)+9)), where n is the number of vertices in the graph and m is the number of edges in the graph. For graphs with minimum degree 2 and girth at least 7, the lower bound can be improved to max\√(n), √((2m)/(3))\, where n and m are the numbers of vertices and edges in the graph respectively. In cases where the graph is of minimum degree 2 and its girth g is at least 12, the lower bound can be further improved to max\√(n), √((\lfloor (g)/(3) \rfloor-1)/(3)m)\.