×

Signed domination in signed graphs. (English) Zbl 1358.05135

Summary: Let \(S= (V,E,\sigma)\) be a signed graph, a function \(f: V\to\{-1, +1\}\) is a signed domination function (SDF) of \(S\) if \(f(N[v])\geq 1\), where \[ f(N[v])= f(v)+ \sum_{u\in N(v)} \sigma(uv)f(u), \] for every \(v\in V\). Every graph can be viewed as a signed graph in which every edge is positive and every graph admits a signed dominating function but it is not true in case of heterogeneous signed graphs (i.e., signed graph possessing at least one negative edge).
In this paper we characterize some classes of signed graphs which admit the signed domination function and we have also shown that signed graph can be embedded as an induced subgraph of a signed graph that admits an SDF.

MSC:

05C22 Signed and weighted graphs
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
PDFBibTeX XMLCite