Using edge contractions to reduce the semitotal domination number

Esther Galby; Paloma Thomé de Lima; Felix Mann; Bernard Ries

doi:10.1016/j.tcs.2022.10.020

Using edge contractions to reduce the semitotal domination number

Esther Galby, Paloma Thomé de Lima, Felix Mann, Bernard Ries

Research output: Journal Article or Conference Article in Journal › Journal article › Research › peer-review

Abstract

In this paper, we consider the problem of reducing the semitotal domination number of a given graph by contracting k edges, for some fixed k ≥ 1. We show that this can always be done with at most 3 edge contractions and further characterise those graphs requiring 1, 2 or 3 edge contractions, respectively, to decrease their semitotal domination number. We then study the complexity of the problem for k = 1 and obtain in particular a complete complexity dichotomy for monogenic classes.

Original language	English
Journal	Theoretical Computer Science
Volume	939
ISSN	0304-3975
DOIs	https://doi.org/10.1016/j.tcs.2022.10.020
Publication status	Published - 2023

Keywords

Blocker problem
Edge contraction
Semitotal domination

Access to Document

10.1016/j.tcs.2022.10.020

https://www.sciencedirect.com/science/article/pii/S0304397522006090/pdfft?md5=300dea53aa9a43e871ca3b1ea6856aac&pid=1-s2.0-S0304397522006090-main.pdf

Cite this

@article{1d9a35cd4b8f46efb769c6bc7cfec077,

title = "Using edge contractions to reduce the semitotal domination number",

abstract = "In this paper, we consider the problem of reducing the semitotal domination number of a given graph by contracting k edges, for some fixed k ≥ 1. We show that this can always be done with at most 3 edge contractions and further characterise those graphs requiring 1, 2 or 3 edge contractions, respectively, to decrease their semitotal domination number. We then study the complexity of the problem for k = 1 and obtain in particular a complete complexity dichotomy for monogenic classes.",

keywords = "Blocker problem, Edge contraction, Semitotal domination, Blocker problem, Edge contraction, Semitotal domination",

author = "Esther Galby and {Thom{\'e} de Lima}, Paloma and Felix Mann and Bernard Ries",

year = "2023",

doi = "10.1016/j.tcs.2022.10.020",

language = "English",

volume = "939",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

}

TY - JOUR

T1 - Using edge contractions to reduce the semitotal domination number

AU - Galby, Esther

AU - Thomé de Lima, Paloma

AU - Mann, Felix

AU - Ries, Bernard

PY - 2023

Y1 - 2023

N2 - In this paper, we consider the problem of reducing the semitotal domination number of a given graph by contracting k edges, for some fixed k ≥ 1. We show that this can always be done with at most 3 edge contractions and further characterise those graphs requiring 1, 2 or 3 edge contractions, respectively, to decrease their semitotal domination number. We then study the complexity of the problem for k = 1 and obtain in particular a complete complexity dichotomy for monogenic classes.

AB - In this paper, we consider the problem of reducing the semitotal domination number of a given graph by contracting k edges, for some fixed k ≥ 1. We show that this can always be done with at most 3 edge contractions and further characterise those graphs requiring 1, 2 or 3 edge contractions, respectively, to decrease their semitotal domination number. We then study the complexity of the problem for k = 1 and obtain in particular a complete complexity dichotomy for monogenic classes.

KW - Blocker problem

KW - Edge contraction

KW - Semitotal domination

KW - Blocker problem

KW - Edge contraction

KW - Semitotal domination

U2 - 10.1016/j.tcs.2022.10.020

DO - 10.1016/j.tcs.2022.10.020

M3 - Journal article

SN - 0304-3975

VL - 939

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

Using edge contractions to reduce the semitotal domination number

Abstract

Keywords

Access to Document

Fingerprint

Cite this