On perfect neighborhood sets in graphs

DOI10.1016/S0012-365X(98)00306-9MaRDI QIDQ1297450zbMATH OpenOpenAlexFDO

Authors Gerd H. Fricke, Teresa W. Haynes, Michael A. Henning, Sandra M. Hedetniemi, Stephen T. Hedetniemi

Publication date 9 January 2000

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(98)00306-9

numerical invariants perfect neighbourhood set upper domination number upper perfect neighbourhood number

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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)\).

Recommendations

Cites work

Cited in

(13)

This page was built for publication: On perfect neighborhood sets in graphs

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