2020/02/13 by Magda Dettlaff, Dettlaff, Magda, Magdalena Lemańska +3
Computer Science · Mathematics · #05C05 #05C69 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2002.05389
openalex publication_date 2020/02/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.