Lower bounds on the minus domination and k-subdomination numbers

Liying Kang; Hong Qiao; Erfang Shan; Dingzhu Du

doi:10.1016/S0304-3975(02)00434-6

Lower bounds on the minus domination and k-subdomination numbers

Liying Kang
, Hong Qiao
, Erfang Shan
, Dingzhu Du

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

16 Citations (Scopus)

Abstract

A three-valued function f defined on the vertex set of a graph G = (V,E), f : V → {-1,0,1} is a minus dominating function if the sum of its function values over any closed neighborhood is at least one. That is, for every v ∈ V, f(N[v]) ≥ 1, where N[v] consists of v and all vertices adjacent to v. The weight of a minus function is f(V) = ∑_v∈Vf(v). The minus domination number of a graph G, denoted by γ^-(G), equals the minimum weight of a minus dominating function of G. In this paper, sharp lower bounds on minus domination of a bipartite graph are given. Thus, we prove a conjecture proposed by Dunbar et al. (Discrete Math. 199 (1999) 35), and we give a lower bound on γ_ks(G) of a graph G. © 2002 Elsevier Science B.V. All rights reserved.

Original language	English
Pages (from-to)	89-98
Journal	Theoretical Computer Science
Volume	296
Issue number	1
DOIs	https://doi.org/10.1016/S0304-3975(02)00434-6
Publication status	Published - 2003
Externally published	Yes
Event	Computing and Combinatorics - Guilin, China Duration: 20 Aug 2001 → 23 Aug 2001

Bibliographical note

Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

Funding

This work was supported by NSFC.

Research Keywords

Domination number
K-subdomination
Minus domination

Access Output

10.1016/S0304-3975(02)00434-6Licence: Elsevier user license

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{548e1b599d2043808d6db5d71d7322dc,

title = "Lower bounds on the minus domination and k-subdomination numbers",

abstract = "A three-valued function f defined on the vertex set of a graph G = (V,E), f : V → \{-1,0,1\} is a minus dominating function if the sum of its function values over any closed neighborhood is at least one. That is, for every v ∈ V, f(N[v]) ≥ 1, where N[v] consists of v and all vertices adjacent to v. The weight of a minus function is f(V) = ∑v∈Vf(v). The minus domination number of a graph G, denoted by γ-(G), equals the minimum weight of a minus dominating function of G. In this paper, sharp lower bounds on minus domination of a bipartite graph are given. Thus, we prove a conjecture proposed by Dunbar et al. (Discrete Math. 199 (1999) 35), and we give a lower bound on γks(G) of a graph G. {\textcopyright} 2002 Elsevier Science B.V. All rights reserved.",

keywords = "Domination number, K-subdomination, Minus domination",

author = "Liying Kang and Hong Qiao and Erfang Shan and Dingzhu Du",

note = "Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].; Computing and Combinatorics ; Conference date: 20-08-2001 Through 23-08-2001",

year = "2003",

doi = "10.1016/S0304-3975(02)00434-6",

language = "English",

volume = "296",

pages = "89--98",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

T1 - Lower bounds on the minus domination and k-subdomination numbers

AU - Kang, Liying

AU - Qiao, Hong

AU - Shan, Erfang

AU - Du, Dingzhu

N1 - Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

PY - 2003

Y1 - 2003

N2 - A three-valued function f defined on the vertex set of a graph G = (V,E), f : V → {-1,0,1} is a minus dominating function if the sum of its function values over any closed neighborhood is at least one. That is, for every v ∈ V, f(N[v]) ≥ 1, where N[v] consists of v and all vertices adjacent to v. The weight of a minus function is f(V) = ∑v∈Vf(v). The minus domination number of a graph G, denoted by γ-(G), equals the minimum weight of a minus dominating function of G. In this paper, sharp lower bounds on minus domination of a bipartite graph are given. Thus, we prove a conjecture proposed by Dunbar et al. (Discrete Math. 199 (1999) 35), and we give a lower bound on γks(G) of a graph G. © 2002 Elsevier Science B.V. All rights reserved.

AB - A three-valued function f defined on the vertex set of a graph G = (V,E), f : V → {-1,0,1} is a minus dominating function if the sum of its function values over any closed neighborhood is at least one. That is, for every v ∈ V, f(N[v]) ≥ 1, where N[v] consists of v and all vertices adjacent to v. The weight of a minus function is f(V) = ∑v∈Vf(v). The minus domination number of a graph G, denoted by γ-(G), equals the minimum weight of a minus dominating function of G. In this paper, sharp lower bounds on minus domination of a bipartite graph are given. Thus, we prove a conjecture proposed by Dunbar et al. (Discrete Math. 199 (1999) 35), and we give a lower bound on γks(G) of a graph G. © 2002 Elsevier Science B.V. All rights reserved.

KW - Domination number

KW - K-subdomination

KW - Minus domination

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

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-0037268618&origin=recordpage

U2 - 10.1016/S0304-3975(02)00434-6

DO - 10.1016/S0304-3975(02)00434-6

M3 - RGC 21 - Publication in refereed journal

SN - 0304-3975

VL - 296

SP - 89

EP - 98

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1

T2 - Computing and Combinatorics

Y2 - 20 August 2001 through 23 August 2001

ER -

Lower bounds on the minus domination and k-subdomination numbers

Abstract

Bibliographical note

Funding

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this