Total k -domination in Cartesian product graphs
- PDF / 753,191 Bytes
- 13 Pages / 439.37 x 666.142 pts Page_size
- 2 Downloads / 205 Views
Total k-domination in Cartesian product graphs S. Bermudo1
· J. L. Sanchéz2,3 · J. M. Sigarreta2
© Akadémiai Kiadó, Budapest, Hungary 2017
Abstract Let G = (V, E) be a graph. A set S ⊆ V is a total k-dominating set if every vertex v ∈ V has at least k neighbors in S. The total k-domination number γkt (G) is the minimum cardinality among all total k-dominating sets. In this paper we obtain several tight bounds for the total k-domination number of the Cartesian product of two graphs, and we investigate the relationship between the total k-domination number of the Cartesian product graph with respect to the total k-domination number in the factors of the product. We also study the total k-domination number in certain particular cases of Cartesian products of graphs and determine the exact values of this parameter. Keywords k-Domination · Total k-domination · k-Tuple domination · k-Tuple total domination Mathematics Subject Classification 05C69
1 Introduction We begin by stating some notation and terminology. Denote by G = (V, E) a simple graph of order n = |V | and size m = |E|. For a vertex u ∈ V let N (v) = {u ∈ V : u ∼ v}
B
S. Bermudo [email protected] J. L. Sanchéz [email protected] J. M. Sigarreta [email protected]
1
Department of Economics, Quantitative Methods and Economic History, Universidad Pablo de Olavide, Carretera de Utrera Km. 1, 41013 Seville, Spain
2
Faculty of Mathematics, Autonomous University of Guerrero, Carlos E. Adame 5, Col. La Garita, Acapulco, Guerrero, Mexico
3
Faculty of Computer Science and Mathematics, Holguín University, 80100 Holguín, Cuba
123
S. Bermudo et al.
and N [v] = N (v) ∪ {v}, where u ∼ v means that u and v are adjacent vertices. The degree of a vertex v ∈ V will be denoted by δ(v) = |N (v)|, and δ and Δ represent the minimum and maximum degree of the graph, respectively. For a non-empty subset S ⊆ V , and any vertex v ∈ V , we denote by N S (v) the set of neighbors that v has in S; that is N S (v) = {u ∈ S : u ∼ v}, and δ S (v) = |N S (v)|. The complement of the vertex set S in V is denoted by S, so that N S (v) is the set of neighbors that v has in S = V \S. Given a graph G = (V, E), a set S ⊆ V is a k-dominating set if every vertex v ∈ V \S satisfies δ S (v) ≥ k. The k-domination number γk (G) is the minimum cardinality among all k-dominating sets. When k = 1 we have that γ1 (G) is equal to the domination number γ (G). A set S ⊆ V is a total k-dominating set if every vertex v ∈ V satisfies δ S (v) ≥ k. In such a case, it is necessary to have k ≤ δ and |S| ≥ k + 1. The total k-domination number γkt (G) is the minimum cardinality among all total k-dominating sets. This concept was studied in [2,3,7,8,18], and it was also studied in [6,11,12], where they called it k-tuple total domination number. A total dominating set is a total 1-dominating set, and the total domination number, denoted by γt (G), is the minimum cardinality among all total dominating sets. That is, γt (G) = γ1t (G) (see [5,14]). This parameter has been studied in the C
Data Loading...
