Dominating sets whose closed stars form spanning trees
type: Item
instance of: scholarly article
title: Dominating sets whose closed stars form spanning trees
zbMATH Open document ID: 0876.05045
DOI: 10.1016/0012-365X(95)00334-S
author: Jerrold W. Grossman
published in: Discrete Mathematics
publication date: 1997-06-16T00:00:00Z
review text: For a subset \(W\) of the vertex set \(V(G)\) of a graph \(G\), \(S(W)\) denotes the subgraph of \(G\) consisting of \(W\), of all edges incident to at least one vertex in \(W\) and of all vertices adjacent to at least one vertex of \(W\). If \(S(W)\) contains all vertices of \(G\) and is a forest (or tree), then \(S(W)\) is a spanning star forest, shortly SSF (or spanning star tree SST respectively). Certain variants of SSF and SST in bipartite graphs are BSSF and BSST. If a graph contains an SST, it is called good, else it is called bad. Existence theorems for good and bad graphs satisfying certain inequalities in terms of numbers of vertices and edges are proved. It is stated that almost all graphs have no SSF and almost all bipartite graphs have no BSSF. At the end there are some algorithmic considerations. Among other results, it is stated that the problem to decide whether a given graph has SSF or SST is NP-complete.
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 90B18
zbMATH DE Number: 1021673
zbMATH Keywords: dominating set
zbMATH Keywords: \(A\)-trail
zbMATH Keywords: Eulerian planar graph
zbMATH Keywords: spanning star forest
zbMATH Keywords: spanning star tree
reviewed by: Bohdan Zelinka
MaRDI profile type: Publication
cites work: The NP-completeness of finding A-trails in Eulerian graphs and of finding spanning trees in hypergraphs
cites work: On non-intersecting Eulerian circuits
cites work: On weakly connected domination in graphs
cites work: Eulerian graphs and related topics. Part 1, Volume 1
cites work: Q4198056
cites work: Spanning star trees in regular graphs
cites work: The splittance of a graph
cites work: Topics on domination
cites work: The NP-completeness column: an ongoing guide
cites work: Q3829572
cites work: Set domination in graphs
cites work: Q3895508
cites work: Q4273661
Recommended article: Spanning trees with disjoint dominating and 2-dominating sets
Recommended article: Spanning trees of countable graphs omitting sets of dominated ends
Recommended article: Spanning trees and domination in hypercubes
Recommended article: Spanning Trees and Domination in Hypercubes
Recommended article: Spanning star trees in regular graphs
Recommended article: Closure and spanning \(k\)-trees
Recommended article: Star forests, dominating sets and Ramsey-type problems
Recommended article: Connected Domination and Spanning Trees with Many Leaves
Recommended article: Q4304348
Recommended article: Q5480722
description: scientific article; zbMATH DE number 1021673