Domination subdivision and domination multisubdivision numbers of graphs

DOI10.7151/DMGT.2103MaRDI QIDQ2312062zbMATH OpenOpenAlexWikidataFDO

Authors Joanna Raczek, Jerzy Topp, Magda Dettlaff

Publication date 4 July 2019

Published in Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported

Full work available at URL https://arxiv.org/abs/1310.1345

zbMATH Keywords

computational complexitytreesdominationdomination subdivision numberdomination multisubdivision number

Mathematics Subject Classification ID

Trees (05C05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph theory (05C99)

Abstract: The emph{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 cite{vel} that sd$(T)leq3$ 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 emph{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)leq3$ for any graph $G$. The domination subdivision number and the domination multisubdivision numer of a graph are incomparable in general case, but we show that for trees these two parameters are equal. We also determine domination multisubdivision number for some classes of graphs.

Recommendations

• Paired domination subdivision and multisubdivision numbers of graphs
• Total domination multisubdivision number of a graph
• Domination subdivision numbers of trees
• Domination Subdivision Numbers
• Trees with domination subdivision number one

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 2149834 (Why is no real title available?)
• Disproof of a conjecture on the subdivision domination number of a graph
• Domination and independence subdivision numbers of graphs
• Domination subdivision numbers of trees
• Effect of edge-subdivision on vertex-domination in a graph
• Total domination multisubdivision number of a graph
• Trees with domination subdivision number one

Cited in

(19)

• Disjunctive Total Domination Subdivision Number of Graphs
• Some graphs with double domination subdivision number three
• Domination and independence subdivision numbers of graphs
• Semitotal domination subdivision numbers of graphs
• Changing of the domination number of a graph: edge multisubdivision and edge removal
• scientific article; zbMATH DE number 5238996 (Why is no real title available?)
• Bounding the total domination subdivision number of a graph in terms of its order
• Domination subdivision stable trees
• Block graphs with large paired domination multisubdivision number
• Total domination multisubdivision number of a graph
• Trees with domination subdivision number one
• Total domination subdivision numbers of graphs
• On a conjecture concerning total domination subdivision number in graphs
• The convex domination subdivision number of a graph
• Total domination subdivision numbers of trees
• Multiplicities of subgraphs
• Paired domination subdivision and multisubdivision numbers of graphs
• Edge subdivision and edge multisubdivision versus some domination related parameters in generalized corona graphs
• Complexity of the paired domination subdivision problem

This page was built for publication: Domination subdivision and domination multisubdivision numbers of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2312062)