Super dominating sets in graphs

Let \(G=(V,E)\) be a graph. A subset \(D\) of \(V(G)\) is called a super dominating set if for every \(v \in V(G)-D\) there exists an external private neighbour of \(v\) with respect to \(V(G)-D.\) The minimum cardinality of a super dominating set is called the super domination number of \(G\) and i...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2013-09
Main Authors: Lemańska, M, Swaminathan, V, Venkatakrishnan, Y B, Zuazua, R
Format: Article
Language:English
Subjects:
Apexes
Trees (mathematics)
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 subset \(D\) of \(V(G)\) is called a super dominating set if for every \(v \in V(G)-D\) there exists an external private neighbour of \(v\) with respect to \(V(G)-D.\) The minimum cardinality of a super dominating set is called the super domination number of \(G\) and is denoted by \(\gamma_{sp}(G)\). In this paper some results on the super domination number are obtained. We prove that if \(T\) is a tree with at least three vertices, then \(\frac{n}{2}\leq\gamma_{sp}(T)\leq n-s,\) where \(s\) is the number of support vertices in \(T\) and we characterize the extremal trees.
ISSN:2331-8422