Bounds relating generalized domination parameters

Michael A. Henning; Henda C. Swart

doi:10.1016/0012-365X(93)90567-D

Bounds relating generalized domination parameters

Michael A. Henning, Henda C. Swart

University of KwaZulu-Natal

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

3 Citations (Scopus)

Abstract

The domination number γ(G) and the total domination number γ_t(G) of a graph G are generalized to the K_n-domination number γ_Kn(G) and the total K_n-domination number γ^t_Kn(G) for n≥2, where γ(G)=γ_K₂(G) and γ_t(G)=γ^t_K₂(G). K_n-connectivity is defined and, for every integer n≥2, the existence of a K_n-connected graph G of order at least n+1 for which γ_K₂(G)+γ^t_Kn(G)=( (3n- 2) n²)p(G) is established. We conjecture that, if G is a K_n-connected graph of order at least n+1, then γ_Kn(G)+γ^t_Kn(G)≤( (3n-2) n²)p(G). This conjecture generalizes the result for n=2 of Allan, Laskar and Hedetniemi. We prove the conjecture for n=3. Further, it is shown that if G is a K₃-connected graph of order at least 4 that satisfies the condition that, for each edge e of G, G-e contains at least one K₃-isolated vertex, then γ_K₃(G)+γ^t_K₃(G)≤(3p) 4 and we show that this bound is best possible.

Original language	English
Pages (from-to)	93-105
Number of pages	13
Journal	Discrete Mathematics
Volume	120
Issue number	1-3
DOIs	https://doi.org/10.1016/0012-365X(93)90567-D
Publication status	Published - 12 Sept 1993
Externally published	Yes

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/0012-365X(93)90567-D

Cite this

@article{ff899da878ab4edc8a36f046609b0844,

title = "Bounds relating generalized domination parameters",

abstract = "The domination number γ(G) and the total domination number γt(G) of a graph G are generalized to the Kn-domination number γKn(G) and the total Kn-domination number γtKn(G) for n≥2, where γ(G)=γK2(G) and γt(G)=γtK2(G). Kn-connectivity is defined and, for every integer n≥2, the existence of a Kn-connected graph G of order at least n+1 for which γK2(G)+γtKn(G)=( (3n- 2) n2)p(G) is established. We conjecture that, if G is a Kn-connected graph of order at least n+1, then γKn(G)+γtKn(G)≤( (3n-2) n2)p(G). This conjecture generalizes the result for n=2 of Allan, Laskar and Hedetniemi. We prove the conjecture for n=3. Further, it is shown that if G is a K3-connected graph of order at least 4 that satisfies the condition that, for each edge e of G, G-e contains at least one K3-isolated vertex, then γK3(G)+γtK3 (G)≤(3p) 4 and we show that this bound is best possible.",

author = "Henning, {Michael A.} and Swart, {Henda C.}",

year = "1993",

month = sep,

day = "12",

doi = "10.1016/0012-365X(93)90567-D",

language = "English",

volume = "120",

pages = "93--105",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "1-3",

}

TY - JOUR

T1 - Bounds relating generalized domination parameters

AU - Henning, Michael A.

AU - Swart, Henda C.

PY - 1993/9/12

Y1 - 1993/9/12

N2 - The domination number γ(G) and the total domination number γt(G) of a graph G are generalized to the Kn-domination number γKn(G) and the total Kn-domination number γtKn(G) for n≥2, where γ(G)=γK2(G) and γt(G)=γtK2(G). Kn-connectivity is defined and, for every integer n≥2, the existence of a Kn-connected graph G of order at least n+1 for which γK2(G)+γtKn(G)=( (3n- 2) n2)p(G) is established. We conjecture that, if G is a Kn-connected graph of order at least n+1, then γKn(G)+γtKn(G)≤( (3n-2) n2)p(G). This conjecture generalizes the result for n=2 of Allan, Laskar and Hedetniemi. We prove the conjecture for n=3. Further, it is shown that if G is a K3-connected graph of order at least 4 that satisfies the condition that, for each edge e of G, G-e contains at least one K3-isolated vertex, then γK3(G)+γtK3 (G)≤(3p) 4 and we show that this bound is best possible.

AB - The domination number γ(G) and the total domination number γt(G) of a graph G are generalized to the Kn-domination number γKn(G) and the total Kn-domination number γtKn(G) for n≥2, where γ(G)=γK2(G) and γt(G)=γtK2(G). Kn-connectivity is defined and, for every integer n≥2, the existence of a Kn-connected graph G of order at least n+1 for which γK2(G)+γtKn(G)=( (3n- 2) n2)p(G) is established. We conjecture that, if G is a Kn-connected graph of order at least n+1, then γKn(G)+γtKn(G)≤( (3n-2) n2)p(G). This conjecture generalizes the result for n=2 of Allan, Laskar and Hedetniemi. We prove the conjecture for n=3. Further, it is shown that if G is a K3-connected graph of order at least 4 that satisfies the condition that, for each edge e of G, G-e contains at least one K3-isolated vertex, then γK3(G)+γtK3 (G)≤(3p) 4 and we show that this bound is best possible.

UR - http://www.scopus.com/inward/record.url?scp=0043261588&partnerID=8YFLogxK

U2 - 10.1016/0012-365X(93)90567-D

DO - 10.1016/0012-365X(93)90567-D

M3 - Article

AN - SCOPUS:0043261588

SN - 0012-365X

VL - 120

SP - 93

EP - 105

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1-3

ER -

Bounds relating generalized domination parameters

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this