A probabilistic algorithm for bounding the total restrained domination number of a K1,ℓ -free graph

Ernst J. Joubert

doi:10.1016/j.dam.2024.07.009

A probabilistic algorithm for bounding the total restrained domination number of a K_1,ℓ -free graph

Ernst J. Joubert

Mathematics and Applied Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

Let G=(V,E) be a graph. A set S⊆V is a total restrained dominating set if every vertex is adjacent to a vertex in S, and every vertex in V−S is adjacent to a vertex in V−S. The total restrained domination number of G, denoted γ_tr(G), is the smallest cardinality of a total restrained dominating set of G. In this paper we show that if G is a K_1,ℓ-free graph with δ≥ℓ≥3 and δ≥5, then γ_tr(G)≤n1−[Formula presented]+o_δ(1).

Original language	English
Pages (from-to)	429-439
Number of pages	11
Journal	Discrete Applied Mathematics
Volume	357
DOIs	https://doi.org/10.1016/j.dam.2024.07.009
Publication status	Published - 15 Nov 2024

Keywords

Domination
Graph
Total restrained domination
Upper bound

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/j.dam.2024.07.009

Cite this

@article{4237009730434ad1a9ce18101e30b7b5,

title = "A probabilistic algorithm for bounding the total restrained domination number of a K1,ℓ -free graph",

abstract = "Let G=(V,E) be a graph. A set S⊆V is a total restrained dominating set if every vertex is adjacent to a vertex in S, and every vertex in V−S is adjacent to a vertex in V−S. The total restrained domination number of G, denoted γtr(G), is the smallest cardinality of a total restrained dominating set of G. In this paper we show that if G is a K1,ℓ-free graph with δ≥ℓ≥3 and δ≥5, then γtr(G)≤n1−[Formula presented]+oδ(1).",

keywords = "Domination, Graph, Total restrained domination, Upper bound",

author = "Joubert, \{Ernst J.\}",

note = "Publisher Copyright: {\textcopyright} 2024 Elsevier B.V.",

year = "2024",

month = nov,

day = "15",

doi = "10.1016/j.dam.2024.07.009",

language = "English",

volume = "357",

pages = "429--439",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - A probabilistic algorithm for bounding the total restrained domination number of a K1,ℓ -free graph

AU - Joubert, Ernst J.

PY - 2024/11/15

Y1 - 2024/11/15

N2 - Let G=(V,E) be a graph. A set S⊆V is a total restrained dominating set if every vertex is adjacent to a vertex in S, and every vertex in V−S is adjacent to a vertex in V−S. The total restrained domination number of G, denoted γtr(G), is the smallest cardinality of a total restrained dominating set of G. In this paper we show that if G is a K1,ℓ-free graph with δ≥ℓ≥3 and δ≥5, then γtr(G)≤n1−[Formula presented]+oδ(1).

AB - Let G=(V,E) be a graph. A set S⊆V is a total restrained dominating set if every vertex is adjacent to a vertex in S, and every vertex in V−S is adjacent to a vertex in V−S. The total restrained domination number of G, denoted γtr(G), is the smallest cardinality of a total restrained dominating set of G. In this paper we show that if G is a K1,ℓ-free graph with δ≥ℓ≥3 and δ≥5, then γtr(G)≤n1−[Formula presented]+oδ(1).

KW - Domination

KW - Graph

KW - Total restrained domination

KW - Upper bound

UR - https://www.scopus.com/pages/publications/85200273874

U2 - 10.1016/j.dam.2024.07.009

DO - 10.1016/j.dam.2024.07.009

M3 - Article

AN - SCOPUS:85200273874

SN - 0166-218X

VL - 357

SP - 429

EP - 439

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -