On perfect neighborhood sets in graphs
type: Item
instance of: scholarly article
title: On perfect neighborhood sets in graphs
zbMATH Open document ID: 0928.05047
DOI: 10.1016/S0012-365X(98)00306-9
author: Gerd H. Fricke
author: Teresa W. Haynes
author: Michael A. Henning
author: Sandra M. Hedetniemi
author: Stephen T. Hedetniemi
published in: Discrete Mathematics
publication date: 2000-01-09T00:00:00Z
review text: Two numerical invariants of graphs, namely the upper domination number \(\Gamma(G)\) and the upper perfect neighbourhood number \(\Theta(G)\), are considered and their equality is proved. A subset \(S\) of the vertex set \(V\) of a graph \(G\) is called dominating in \(G\), if each vertex of \(G\) either is in \(S\), or is adjacent to a vertex of \(S\). The maximum number of vertices of a minimal (with respect to set inclusion) dominating set in \(G\) is the upper domination number \(\Gamma(G)\) of \(G\). A vertex \(v\) of \(G\) is said to be \(S\)-perfect, if its closed neighbourhood \(N[v]\) has exactly one vertex in common with \(S\). If every vertex of \(G\) is \(S\)-perfect or adjacent to an \(S\)-perfect vertex, then the set \(S\) is called a perfect neighbourhood set. The maximum number of vertices of a perfect neighbourhood set in \(G\) is the upper perfect neighbourhood number \(\Theta(G)\) of \(G\). The main result of the paper states that \(\Theta(G)= \Gamma(G)\).
reviewed by: Bohdan Zelinka
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 1321806
zbMATH Keywords: numerical invariants
zbMATH Keywords: upper domination number
zbMATH Keywords: perfect neighbourhood set
zbMATH Keywords: upper perfect neighbourhood number
MaRDI profile type: Publication
cites work: Q4350166
cites work: Irredundant and perfect neighbourhood sets in trees
cites work: Q4943531
cites work: Q4368728
cites work: Q4368729
full work available at URL: s0012-365x(98)00306-9
OpenAlex ID: W2005145220
description: scientific article; zbMATH DE number 1321806