Signed domatic number of a graph

DOI10.1016/J.DAM.2004.08.010MaRDI QIDQ2565862zbMATH OpenOpenAlexFDO

Authors Lutz Volkmann, Bohdan Zelinka

Publication date 28 September 2005

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/18148

zbMATH Keywords

signed dominating function signed domination number

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Review text

Given a graph \(G=(V, E)\), the signed dominating function is a two-valued mapping \(f : V \rightarrow \{-1, 1\}\) such that, for each vertex \(v\in V\), \(\sum_{x\in N[v]} f(x) \geq 1\), where \(N[v]=N(v)\cup\{v\}\) is the closed neighborhood of \(v\). A signed dominating family on \(G\) is a set \(\{f_1, f_2, \ldots, f_d\}\) of signed dominating functions on \(G\) with the property that \(\sum_{i=1}^d f_i(x) \leq 1\) for each \(x\in V\). The maximum number of functions in a signed dominating family on \(G\), denoted by \(d_S(G)\), is the signed dominatic number of \(G\). The authors point out that \(d_S(G)\) is well defined and study its basic properties. Among others, they show that \(d_S(G)\) is an odd integer between \(1\) and the minimum degree of \(G\) plus one. They then determine \(d_S(G)\) in case \(G\) is a tree, a complete graph, a cycle, a fan, or a wheel, where a fan (wheel) is a graph obtained from a path (cycle) by adding a new vertex and edges joining it to all the vertices of the path (cycle).

Recommendations

Cites work

Cited in

(17)

This page was built for publication: Signed domatic number of a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2565862)