angielski

Magda Dettlaff; Magdalena Lemańska; Adriana Roux

angielski

Abstract

A subset D of V (G) is a dominating set of a graph G if every vertex of V (G) − D has at least one neighbour in D; let the domination number γ(G) be the minimum cardinality among all dominating sets in G. We say that a graph G is γ-q-critical if subdividing any q edges results in a graph with domination number greater than γ(G) and there exists a set of q − 1 edges such that subdividing these edges results in a graph with domination number γ(G). In this paper we consider mainly γ-qcritical trees and give some general properties of γ-q-critical graphs; in particular, we characterize those trees T that are γ-(n(T) − 1)-critical. We also characterize γ-2-critical trees T with sd(T) = 2 and γ-3-critical trees T with sd(T) = 3, where the domination subdivision number sd(G) of a graph G is the minimum number of edges which must be subdivided (where each edge can be subdivided at most once) to construct a graph with domination number greater than γ(G).