2020/02/13 by Magda Dettlaff, Dettlaff, Magda, Magdalena Lemańska +4
Computer Science · Mathematics · #05C05 #05C69 #Advanced Graph Theory Research #Cardinality (data modeling) #Combinatorics #Combinatorics (math.CO) #Computer science #Discrete mathematics #FOS: Mathematics #Graph #Graph theory and applications #Interconnection Networks and Systems #Mathematics #Subdivision #Tree (set theory) #Vertex (graph theory) #math.CO #msc:05C05 #msc:05C69
paper · pdf · doi:10.48550/arxiv.2002.05389
published in arXiv (Cornell University) (Cornell University) · 11 pages, 1 figure
arxiv created 2020/02/13 · openalex publication_date 2020/02/13 · arxiv updated 2020/02/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/08
A subset D of V is dominating in G if every vertex of V-D has at least one neighbour in D; let γ(G) be the minimum cardinality among all dominating sets in G. A graph G is γ-q-\it critical if the smallest subset of edges whose subdivision necessarily increases γ(G) has cardinality q. In this paper we consider mainly γ-q-critical trees and give some general properties of gamma-q-critical graphs. In particular, we show that if T is a γ-q-critical tree, then 1 ≤ q ≤ n(T)-1 and we characterize extremal trees when q=n(T)-1. Since a subdivision number of a tree T \rm sd(T) is always 1,2 or 3, we also characterize γ-2-critical trees T with \rm sd(T)=2 and γ-3-critical trees T with \rm sd(T)=3.