Dominating sets whose closed stars form spanning trees

Trees (05C05) Extremal problems in graph theory (05C35) Eulerian and Hamiltonian graphs (05C45) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Communication networks in operations research (90B18)

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.

Recommendations

Cites work

Cited in

(6)

This page was built for publication: Dominating sets whose closed stars form spanning trees

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