Partitioning the Vertices of a Cubic Graph Into Two Total Dominating Sets
Document Type
Article
Publication Date
5-31-2017
Description
A total dominating set in a graph G is a set S of vertices of G such that every vertex in G is adjacent to a vertex of S. We study cubic graphs whose vertex set can be partitioned into two total dominating sets. There are infinitely many examples of connected cubic graphs that do not have such a vertex partition. In this paper, we show that the class of claw-free cubic graphs has such a partition. For an integer k at least 3, a graph is k-chordal if it does not have an induced cycle of length more than k. Chordal graphs coincide with 3-chordal graphs. We observe that for k≥6, not every graph in the class of k-chordal, connected, cubic graphs has two vertex disjoint total dominating sets. We prove that the vertex set of every 5-chordal, connected, cubic graph can be partitioned into two total dominating sets. As a consequence of this result, we observe that this property also holds for a connected, cubic graph that is chordal or 4-chordal. We also prove that cubic graphs containing a diamond as a subgraph can be partitioned into two total dominating sets.
Citation Information
Desormeaux, Wyatt J.; Haynes, Teresa W.; and Henning, Michael A.. 2017. Partitioning the Vertices of a Cubic Graph Into Two Total Dominating Sets. Discrete Applied Mathematics. Vol.223 52-63. https://doi.org/10.1016/j.dam.2017.01.032 ISSN: 0166-218X