The exact 2-domination number of generalized Petersen graphs
- PDF / 225,660 Bytes
- 6 Pages / 510.236 x 680.315 pts Page_size
- 20 Downloads / 203 Views
The exact 2-domination number of generalized Petersen graphs XUE-GANG CHEN∗
and XUE-SONG ZHAO
Department of Mathematics, North China Electric Power University, Beijing 102206, China *Corresponding author. E-mail: [email protected]
MS received 21 November 2019; revised 27 February 2020; accepted 6 March 2020 Abstract. Let G = (V, E) be a graph. A subset S ⊆ V is a 2-dominating set of G if each vertex in V − S is adjacent to at least two vertices in S. The 2-domination number of G is the cardinality of the smallest 2-dominating set of G. In this paper, we shall prove that the 2-domination number of generalized Petersen graphs P(5k + 1, 3), P(5k + 2, 3) and P(5k + 3, 3) is 4k + 2, 4k + 3 and 4k + 4, respectively. This proves one conjecture due to Bakhshesh et al. (Proc. Indian Acad. Sci. (Math. Sci.) 128 (2018) 17). Keywords.
2-Domination number; generalized Petersen graph.
Mathematics Subject Classification.
05C69, 05C35.
1. Introduction Graph theory terminology not presented here can be found in [1]. Let G = (V, E) be a graph with |V | = n. The degree, neighborhood and closed neighborhood of a vertex v in the graph G are denoted by dG (v), N G (v) and N G [v] = N G (v) ∪ {v}, respectively. If the graph G is clear from context, we simply write d(v), N (v) and N [v], respectively. The minimum degree and maximum degree of the graph G are denoted by δ(G) and (G), respectively. The graph induced by S ⊆ V is denoted by G[S]. The diameter of G, denoted by diam(G), is the maximum distance among pairs of vertices in G. For any subset S ⊆ V , let E(S, V − S) = {e ∈ E(G) : e = uv, u ∈ S, v ∈ V − S}. A subset S ⊆ V is a k-dominating set of G if each vertex in V − S is adjacent to at least k vertices in S. The minimum size of a k-dominating set in G is called k-domination number of G and is denoted by γk (G). A k-dominating set of G with the minimum cardinality is called a γk -set of G. The k-domination number of a graph was introduced by Fink and Jacobson [3]. The generalized Petersen graph P(n, nk) = (V, E) is defined as follows: V = {v1 , v2 , . . . , vn , u 1 , u 2 , . . . , u n }, E = i=1 {(vi , u i ), (vi , vi+1 ), (u i , u i+k )}, where the subscripts are taken modulo n. The problem of finding the domination number of generalized Petersen graphs has been considered by some researchers in [4] and [5]. The 2-domination number of generalized Petersen graphs was considered by Cheng [2]. He determined the exact value on the 2domination number of generalized Petersen graphs P(5k, 2), P(5k+3, 2) and P(5k+4, 2). In particular, he gave the following. © Indian Academy of Sciences 0123456789().: V,-vol
54
Page 2 of 6
Proc. Indian Acad. Sci. (Math. Sci.)
(2020) 130:54
PROPOSITION 1 For k > 0 and 0 ≤ t < k, γ2 (P(5k, 5t + 3)) = 4k. Bakhshesh et al. [1] determined the exact value on the 2-domination number of generalized Petersen graphs P(5k + 1, 2) and P(5k + 2, 2). In particular, he gave the following. PROPOSITION 2 For each k > 0, γ2 (P(5k + 4, 3)) = 4k + 4. Furthermore, they gave a good lower and upper bounds on the 2-d
Data Loading...
