Partitioning Claw-Free Subcubic Graphs into Two Dominating Sets
2020
A dominating set in a graph G is a set $$S\subseteq V(G)$$ such that every vertex in $$V(G){\setminus } S$$ has at least one neighbor in S. Let G be an arbitrary claw-free graph containing only vertices of degree two or three. In this paper, we prove that the vertex set of G can be partitioned into two dominating sets $$V_1$$ and $$V_2$$ such that for $$i=1,2$$, the subgraph of G induced by $$V_i$$ is triangle-free and every vertex $$v\in V_i$$ also has at least one neighbor in $$V_i$$ if v has degree three in G. This gives an affirmative answer to a problem of Bacso et al. and generalizes a result of Desormeaux et al.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
12
References
0
Citations
NaN
KQI