Partitioning Claw-Free Subcubic Graphs into Two Dominating Sets
- PDF / 580,209 Bytes
- 18 Pages / 439.37 x 666.142 pts Page_size
- 33 Downloads / 254 Views
(0123456789().,-volV)(0123456789().,-volV)
ORIGINAL PAPER
Partitioning Claw-Free Subcubic Graphs into Two Dominating Sets Qing Cui1 Received: 27 September 2019 / Revised: 19 April 2020 Ó Springer Japan KK, part of Springer Nature 2020
Abstract A dominating set in a graph G is a set S VðGÞ such that every vertex in VðGÞnS 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 V1 and V2 such that for i ¼ 1; 2, the subgraph of G induced by Vi is triangle-free and every vertex v 2 Vi also has at least one neighbor in Vi 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 Dominating set Claw-free Subcubic graph
Mathematics Subject Classification 05C69 05C70
1 Introduction We only consider finite graphs without loops or multiple edges. Let G be a graph with vertex set V(G) and edge set E(G). A vertex of G is said to be a k-vertex if it has degree k in G. For any vertex v 2 VðGÞ, the open neighborhood NG ðvÞ of v is the set of vertices adjacent to v in G, and the closed neighborhood NG ½v of v is NG ðvÞ [ fvg. If there is no ambiguity, we simply write N(v) and N[v] instead of NG ðvÞ and NG ½v, respectively. For any S VðGÞ, we use G[S] to denote the subgraph of G induced by S. For a graph H, we say that G is H-free if it does not This work was supported by the Fundamental Research Funds for the Central Universities (No. NS2020055) and the National Natural Science Foundation of China (No. 11501291). & Qing Cui [email protected] 1
Department of Mathematics, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, People’s Republic of China
123
Graphs and Combinatorics
contain H as an induced subgraph. In particular, if H ffi K1;3 , then we say that G is claw-free. An edge e 2 EðGÞ is flat if it is not contained in any triangle of G. A graph is subcubic if it has maximum degree at most three. A dominating set in a graph G is a set S VðGÞ such that every vertex in VðGÞnS has at least one neighbor in S. A total dominating set of G is a set S VðGÞ such that every vertex in V(G) has at least one neighbor in S. A paired-dominating set S of G is a total dominating set with the additional property that G[S] contains a perfect matching. The study of domination and its variations in graphs is one of the most popular subjects in graph theory and has been investigated extensively in the literature (see [5–7, 9] and the references cited therein). Let G be a graph without isolated vertices and let S be a maximal independent set in G. It is easy to see that both S and VðGÞnS are dominating sets of G. This implies that the vertex set of every graph with minimum degree at least one can be partitioned into two dominating sets. The same result does not hold if dominating sets are replaced by total dominating sets since Zelinka [12] showed that for any integer k 1
Data Loading...
