DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


Authors:

C.M. Mynhardt, J. Raczek

Title:

Block graphs with large paired domination multisubdivision number

Source:

Discussiones Mathematicae Graph Theory

Received: 2018-06-27, Revised: 2018-12-28, Accepted: 2019-05-16, https://doi.org/10.7151/dmgt.2230

Abstract:

The paired domination multisubdivision number of a nonempty graph $G$, denoted by $\operatorname{msd}_{\operatorname{pr}}(G)$, is the smallest positive integer $k$ such that there exists an edge which must be subdivided $k$ times to increase the paired domination number of $G$. It is known that $\operatorname{msd}_{\operatorname{pr}}(G)\leq4$ for all graphs $G$. We characterize block graphs with $\operatorname{msd}_{\operatorname{pr}}(G)=4$.

Keywords:

paired domination, domination subdivision number, domination multisubdivision number, block graph

PDF
Close