Upper signed domination number

Let G = ( V , E ) be a graph. A signed dominating function on G is a function f : V → { - 1 , 1 } such that ∑ u ∈ N [ v ] f ( u ) ⩾ 1 for each v ∈ V , where N [ v ] is the closed neighborhood of v . The weight of a signed dominating function f is ∑ v ∈ V f ( v ) . A signed dominating function f is m...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2008-08, Vol.308 (15), p.3416-3419
Main Authors: Tang, Huajun, Chen, Yaojun
Format: Article
Language:English
Subjects:
Applied sciences
Computer science
control theory
systems
Exact sciences and technology
Information retrieval. Graph
Theoretical computing
Upper bound
Upper signed domination number
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let G = ( V , E ) be a graph. A signed dominating function on G is a function f : V → { - 1 , 1 } such that ∑ u ∈ N [ v ] f ( u ) ⩾ 1 for each v ∈ V , where N [ v ] is the closed neighborhood of v . The weight of a signed dominating function f is ∑ v ∈ V f ( v ) . A signed dominating function f is minimal if there exists no signed dominating function g such that g ≠ f and g ( v ) ⩽ f ( v ) for each v ∈ V . The upper signed domination number of a graph G, denoted by Γ s ( G ) , equals the maximum weight of a minimal signed dominating function of G. In this paper, we establish an tight upper bound for Γ s ( G ) in terms of minimum degree and maximum degree. Our result is a generalization of those for regular graphs and nearly regular graphs obtained in [O. Favaron, Signed domination in regular graphs, Discrete Math. 158 (1996) 287–293] and [C.X. Wang, J.Z. Mao, Some more remarks on domination in cubic graphs, Discrete Math. 237 (2001) 193–197], respectively.
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2007.06.031