Domination subdivision and domination multisubdivision numbers of graphs

DOI10.7151/DMGT.2103zbMATH Open1415.05131arXiv1310.1345OpenAlexW2964045359WikidataQ129756515 ScholiaQ129756515MaRDI QIDQ2312062FDOQ2312062

Authors: Joanna Raczek, Jerzy Topp, Magda Dettlaff 

Publication date: 4 July 2019

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Disproof of a conjecture on the subdivision domination number of a graph
• Effect of edge-subdivision on vertex-domination in a graph
• Domination subdivision numbers of trees
• Trees with domination subdivision number one
• Title not available (Why is that?)
• Domination and independence subdivision numbers of graphs
• Total domination multisubdivision number of a graph

Cited In (19)

• 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
• Title not available (Why is that?)
• 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
• Trees with domination subdivision number one
• Total domination multisubdivision number of a graph
• 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
• Paired domination subdivision and multisubdivision numbers of graphs
• Multiplicities of subgraphs
• Edge subdivision and edge multisubdivision versus some domination related parameters in generalized corona graphs
• Complexity of the paired domination subdivision problem
• Disjunctive Total Domination Subdivision Number of Graphs

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)