Search Results

You are looking at 1 - 2 of 2 items for

  • Author: Jerzy Topp x
Clear All Modify Search
Open access

Magda Dettlaff, Joanna Raczek and Jerzy Topp

Abstract

The domination subdivision number sd(G) of a graph G is the minimum number of edges that must be subdivided (where an edge can be subdivided at most once) in order to increase the domination number of G. It has been shown [10] that sd(T) ≤ 3 for any tree T. We prove that the decision problem of the domination subdivision number is NP-complete even for bipartite graphs. For this reason we define the domination multisubdivision number of a nonempty graph G as a minimum positive integer k such that there exists an edge which must be subdivided k times to increase the domination number of G. We show that msd(G) ≤ 3 for any graph G. The domination subdivision number and the domination multisubdivision number of a graph are incomparable in general, but we show that for trees these two parameters are equal. We also determine the domination multisubdivision number for some classes of graphs.

Open access

Joanna Cyman, Michael A. Henning and Jerzy Topp

Abstract

A dominating set of a graph G is a subset DVG such that every vertex not in D is adjacent to at least one vertex in D. The cardinality of a smallest dominating set of G, denoted by γ(G), is the domination number of G. The accurate domination number of G, denoted by γ a(G), is the cardinality of a smallest set D that is a dominating set of G and no |D|-element subset of VG \ D is a dominating set of G. We study graphs for which the accurate domination number is equal to the domination number. In particular, all trees G for which γ a(G) = γ(G) are characterized. Furthermore, we compare the accurate domination number with the domination number of different coronas of a graph.