Dominating sets whose closed stars form spanning trees (Q1357724): Difference between revisions

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.