An Improved Upper Bound on the Total Restrained Domination Number in Cubic Graphs |
| |
Authors: | Justin Southey Michael A. Henning |
| |
Affiliation: | 1. Department of Mathematics, University of Johannesburg, Auckland Park, 2006, South Africa
|
| |
Abstract: | In this paper, we continue the study of total restrained domination in graphs. A set S of vertices in a graph G = (V, E) is a total restrained dominating set of G if every vertex of G is adjacent to some vertex in S and every vertex of ${V {setminus} S}$ is adjacent to a vertex in ${V {setminus} S}$ . The minimum cardinality of a total restrained dominating set of G is the total restrained domination number γ tr(G) of G. Jiang et?al. (Graphs Combin 25:341–350, 2009) showed that if G is a connected cubic graph of order n, then γ tr(G) ≤ 13n/19. In this paper we improve this upper bound to γ tr(G) ≤ (n?+?4)/2. We provide two infinite families of connected cubic graphs G with γ tr(G) = n/2, showing that our new improved bound is essentially best possible. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|