Partitioning the vertices of a graph or its complement into a total dominating set and an independent dominating set

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) Structural characterization of families of graphs (05C75)

Review text

The theme of this paper is around the class of graphs whose vertex set can be partitioned into two sets one of which is an independent set whereas the other is a total dominating set, that is, a dominating set that has no isolated vertices. Such a graph is abbreviated as a TI graph. The authors identify a family of graphs such that for any graph \(G\) either \(G\) or the complement of \(G\) is a TI graph if and only if \(G\) does not belong to this family. The other main result of this paper characterises when the complementary prism of a graph \(G\) is a TI graph. (The complementary prism of a graph \(G\) is the disjoint union of \(G\) with its complement with the corresponding vertices being adjacent.) Basically, this result identifies two specific graphs such that the complementary prism is a TI graph unless it is one of these two graphs. Other types of prisms are also considered.

Recommendations

Cites work

Cited in

(3)

This page was built for publication: Partitioning the vertices of a graph or its complement into a total dominating set and an independent dominating set

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