1. On Upper Total Domination Versus Upper Domination in Graphs.
- Author
-
Zhu, Enqiang, Liu, Chanjuan, Deng, Fei, and Rao, Yongsheng
- Subjects
DOMINATING set ,GRAPH connectivity ,GEODESICS ,GEOMETRIC vertices ,REGULAR graphs - Abstract
A total dominating set of a graph G is a dominating set S of G such that the subgraph induced by S contains no isolated vertex, where a dominating set of G is a set of vertices of G such that each vertex in V (G) \ S has a neighbor in S. A (total) dominating set S is said to be minimal if S \ { v } is not a (total) dominating set for every v ∈ S . The upper total domination number Γ t (G) and the upper domination number Γ (G) are the maximum cardinalities of a minimal total dominating set and a minimal dominating set of G, respectively. For every graph G without isolated vertices, it is known that Γ t (G) ≤ 2 Γ (G) . The case in which Γ t (G) Γ (G) = 2 has been studied in Cyman et al. (Graphs Comb 34:261–276, 2018), which focused on the characterization of the connected cubic graphs and proposed one problem to be solved and two questions to be answered in terms of the value of Γ t (G) Γ (G) . In this paper, we solve this problem, i.e., the characterization of the subcubic graphs G that satisfy Γ t (G) Γ (G) = 2 , by constructing a class of subcubic graphs, which we call triangle-trees. Moreover, we show that the answers to the two questions are negative by constructing connected cubic graphs G that satisfy Γ t (G) Γ (G) > 3 2 and a class of regular non-complete graphs G that satisfy Γ t (G) Γ (G) = 2 . [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF