1. Introduction and Preliminary Results
In general, we will use the standard terminology and notation of graph theory (see [
1]).
We consider only simple and undirected graphs. The graph
is an empty graph and
G is trivial if it is empty or
. If
, then
G is nontrivial. We say that a subset
is dominating if every vertex of
G is either in
D or it is adjacent to at least one vertex of
D. Dominating sets is one of the most intensively studied concepts in graph theory. Through decades, many new types of dominating sets have been introduced and researched; some recent results were obtained, for example, in [
2,
3,
4,
5].
A subset is independent if no two vertices of S are adjacent in G. An independent set is maximal if it is not a proper subset of any other independent set. Maximum cardinality of an independent set in the graph G we denote by , whereas minimum cardinality of a maximal independent set (or, equivalently, an independent dominating set) in G we denote by . By we denote the number of all maximal independent sets in G.
A subset
J being dominating and independent is called a kernel of
G. The concept of kernels was introduced by von Neumann and Morgenstern in digraphs in their research in game theory (see [
6]). Since then, kernels in graphs were studied in the next decades, for examples, see [
7,
8,
9,
10]. The issue of the existence of kernels in undirected graphs is trivial, since every maximal independent set is a kernel.
However, if we place some additional restrictions on the subset of vertices, modifying the classical concepts of domination or independence, the problem of the existence becomes more complicated. By doing so, many types of kernels in undirected graphs were introduced and studied, for example,
-kernels [
11,
12,
13], efficient dominating sets [
14], restrained independent dominating sets [
15], strong (1,1,2)-kernels [
16], and many others.
Some types of kernels obtained in this way are related to multiple domination. This concept was introduced by J. F. Fink and M. S. Jacobson in [
17]. For any integer
, a subset
is called a
p-dominating set of
G if every vertex from
has at least
p neighbors in
D. For
, we get the classical definition of the dominating set. If
, then we obtain the 2-dominating set. Based on the definition of the 2-dominating set in [
18], A. Włoch introduced and studied the concept of a 2-dominating kernel. A set
J is a 2-dominating kernel of a graph
G if it is independent and 2-dominating.
In [
19], Hedetniemi et al. introduced so-called secondary domination. For a positive integer
k, we say that the set
is
-dominating if for every
there exist distinct vertices
such that
and
. By combining this type of domination with independence, we obtain
-kernels, i.e., subsets, which are independent and
-dominating. Let us observe that
-kernels are equivalent to 2-dominating kernels. In general, the problem of the existence of secondary dominating kernels is
-complete (see [
19,
20]). Some problems concerning
-kernels in trees, graph products, and generalized Petersen graphs were considered in [
20,
21,
22,
23,
24], while
-kernels were studied, among others, in [
19,
25].
In our considerations we will use the following notation:
the number of all -kernels in G.
the lower -kernel number, i.e. minimum cardinality of a -kernel in G.
the upper -kernel number, i.e. maximum cardinality of a -kernel in G.
This paper concerns the problem of the existence and the number of -kernels and -kernels in generalized graph products such as the generalized corona of graphs and the G-join of graphs. The main results of the paper are:
Obtaining necessary and sufficient conditions for the existence of -kernels and -kernels as well as determining general formulas for parameters , , and in the generalized corona.
Giving complete characterization of the G-join with -kernels and applying them to describe those kernels in other graph operations such as the join, the composition, and the duplication of vertices.
2. -Kernels in the Generalized Corona of Graphs
In this section, we consider the problem of the existence and the number of
-kernels in the generalized corona of graphs. The classical definition of the corona of two graphs was introduced by R. Frucht and F. Harary in [
26]. Problems of independence and domination in the generalized corona of graphs were considered in [
10,
27,
28].
First, we give the definition of the generalized corona of graphs. Let G be a graph such that , and let be a sequence of arbitrary graphs, where is the set of indices. The generalized corona of a graph G and the sequence is the graph such that and
Figure 1 shows the generalized corona
.
Now, we give necessary and sufficient conditions for the existence of -kernels in the generalized corona of graphs, where all of the graphs from the sequence are nontrivial.
Theorem 1. Let G be an arbitrary graph with vertices and be a sequence of n nontrivial graphs. The graph has a -kernel if, and only if, all graphs , have a -kernel.
Proof. Assume that graphs , have a -kernel . Since graphs are nontrivial, . Thus, . We will show that for an arbitrary graph G of order , the set is a -kernel of a graph . From the definition of the generalized corona of graphs it follows that J is an independent set. Since , every vertex of a graph G has at least two neighbors in the set . Hence, J is a -kernel of a graph .
Conversely, let us assume that a certain graph , has a -kernel J. We will show that . Let , , and suppose by the contrary that . Then, . Since , the set J is not 2-dominating, a contradiction with the assumption that J is a -kernel. Hence, . Since the graph has a -kernel J and , graphs , must have a -kernel . Moreover, every vertex has at least two neighbors in the set . Therefore, , and hence , which ends the proof. □
Based on the proof of Theorem 1, the following corollary is obtained. It concerns the number of -kernels in the generalized corona of graphs as well as the lower and upper -kernel numbers.
Corollary 1. Let G be an arbitrary graph with vertices and be a sequence of n nontrivial graphs. If graphs have a -kernel, then
- 1.
- 2.
- 3.
Now, let us consider the case where graphs from the sequence are arbitrary. Let be a sequence of arbitrary graphs. In particular, graphs from the sequence can be trivial or empty. Let , where , , . We give the complete characterization of the generalized corona of graphs with a -kernel.
Theorem 2. Let G be an arbitrary graph with vertices and be a sequence of n arbitrary graphs. The graph has a -kernel if, and only if, each graph , has a -kernel and the subgraph has a -kernel.
Proof. Let us assume that a certain graph has a -kernel J. Then, each graph , must have a -kernel to 2-dominate vertices from the set . Since , , the subgraph must have a -kernel.
Conversely, let us assume that each graph , has a -kernel and the subgraph has a -kernel . We will show that the set is a -kernel of the graph . The independence of the set J follows from the definition of the generalized corona of graphs. Thus, it is sufficient to show that the set J is 2-dominating. Let . If , , then the vertex v is 2-dominated by the set . If , then the vertex v has at least two neighbors in the set . This means that the set J is a -kernel of the graph , which ends the proof. □
By the construction of -kernels in the generalized corona of graphs shown in the proof above, we obtain the following corollary.
Corollary 2. Let G be an arbitrary graph with vertices and be a sequence of n arbitrary graphs and let . If the graph has a -kernel, then
- 1.
- 2.
- 3.
Finally, we give another complete characterization of the generalized corona of arbitrary graphs.
Theorem 3. Let G be an arbitrary graph with vertices and be a sequence of n arbitrary graphs. The graph has a -kernel if, and only if, the following conditions hold:
- (i)
Each graph , has a -kernel.
- (ii)
The subgraph induced by the set has a -kernel .
- (iii)
For there exists such that and .
Proof. Let us assume that a certain graph has a -kernel J. Then, each graph , must have a -kernel to 2-dominate vertices from the set . Thus, the condition (i) holds. We will show that the subgraph induced by the set has a -kernel. If , then . Otherwise, the set J is not independent. Let . Since J is a -kernel of the graph , the set is a -kernel of the subgraph induced by the set . Hence, the condition (ii) holds. For all , we have . To 2-dominate vertices , there must exist , such that . Thus, the condition (iii) holds.
Conversely, let us assume that conditions (i)–(iii) hold. We will show that the graph has a -kernel , where is a -kernel of the graph for and is a -kernel of the subgraph induced by the set . The independence of the set J follows from the definition of . Thus, it is sufficient to show that the set J is 2-dominating. Let . If , , then the vertex v is 2-dominated by the set . If , , then the vertex v is 2-dominated by the set . If , , then the vertex v is 2-dominated by the set . Hence, the set J is a -kernel of the graph , which ends the proof. □
Figure 2 shows the generalized corona
and an example of a
-kernel in this graph.
3. -Kernels in the Generalized Corona of Graphs
In this section, we study the existence of -kernels in the generalized corona. Let . The set we will refer to as the k-th weak neighborhood of the vertex x in the graph G. In particular, the set we refer to as the second weak neighborhood of x.
Let be the set of indices. We denote as follows: by , the set and by , the set . For simplicity, the subgraph of G induced by the set , we denote by .
Let us begin with proving lemmas, which will be helpful in our next considerations concerning the complete characterization of generalized corona with -kernels.
Lemma 1. Let J be a -kernel in the generalized corona . If , then .
Proof. Let J be a -kernel. By contradiction, let us suppose that and . It follows that no vertex of the graph belongs to J. Moreover, for any such that , we have . This means that for any vertex , we have , which means that y is not -dominated by J, a contradiction. □
Lemma 2. Let have a -kernel. If , then there exists such that .
Proof. Let have a -kernel J. For the sake of contradiction, let us assume that for some , there is no such that . By Lemma 1, we know that . Moreover, any other neighbor of in G also does not belong to J. This means that the intersection of sets and J consists of unique vertex , which dominates all other vertices of and the vertex , but it implies that for all vertices , we have , which means they are not -dominated, a contradiction. □
Now, we are ready to present necessary and sufficient conditions for a generalized corona of graphs to have a -kernel.
Theorem 4. Let G be an arbitrary connected, nontrivial graph, be a sequence of graphs such that . The generalized corona has a -kernel if, and only if, .
Proof. First, we prove the sufficient condition. Let us assume that , i.e., for any , the graph is not isomorphic to . In each graph we take an independent set of maximum cardinality and denote it by . Let us consider the set . Clearly, J is independent in . We show that it is -dominating. Let . First, let ; this means for some . If , then the is -dominated by . If , then is dominated by and there exists a path of length 2. Now, we assume that v belongs to for some . The set is dominating in and has at least two vertices, say . This means v is dominated by at least one of them, say and, by the definition of generalized corona, there exists a path . Hence, J is -dominating.
To prove the necessary condition, let us suppose that has a -kernel J. For the sake of contradiction, let . By Lemma 2, it means that . A contradiction with the assumption that means that . □
From the proof of Theorem 4, we may conclude a corollary concerning the number of all -kernels as well as lower and upper -kernel numbers in some cases of generalized corona.
Corollary 3. Let G be an arbitrary, connected, nontrivial graph with n vertices and be a sequence of n arbitrary graphs such that for all .
- 1.
- 2.
- 3.
Now, we consider a more general concept, i.e., we allow that graphs from the sequence can be empty.
Theorem 5. Let G be an arbitrary connected non-empty graph, be a sequence of graphs, and . The generalized corona has a -kernel if, and only if, the subgraph has a maximal independent set S such that the following conditions hold:
- (i)
If , then there exists such that and
- (ii)
For every vertex at least one of the following conditions is satisfied:
- (a)
There exists such that .
- (b)
is -dominated by the set S.
Proof. First, we will prove the sufficient condition. Let us assume that the subgraph has a maximal independent set S such that conditions (i) and (ii) are satisfied. We will show that has a -kernel. If , then in the graph we take any independent set of the maximum cardinality and denote it by . Let . It is easy to see that J is independent. We will show it is -dominating. Let us divide all vertices lying outside J into four cases.
First, let be such that the graph has at least two vertices and is not complete. Then, is -dominated by and for all , we have .
Second, let be such that . If the vertex has a neighbor such that , then . Therefore, let us suppose that for all j such that , we have . If there exists such that , then is -dominated by the set . Otherwise, by maximality of S in we obtain . Hence, is -dominated by J.
Third, let . Then, by the condition (i), the vertex is -dominated by the set and for all , we have .
Fourth, let . Then, by maximality of S in and the condition (ii), we have or , where and .
This means that the set J is -dominating in , hence it is a -kernel.
Now, we prove the necessary condition. Let us suppose that has a -kernel J. For the sake of contradiction, let us assume that in the subgraph , no maximal independent set satisfies both conditions (i) and (ii). This means that for every maximal independent set S of :
There exists such that has no neighbor in S or
There exists a vertex , which is neither -dominated by S nor has a neighbor .
Since the intersection of J and must be a maximal independent set in , we obtain that we always find at least one vertex , which is not -dominated by J, or a vertex , which is not -dominated by J. This is a contradiction with the fact that J is a -kernel. Hence, there must exist a maximal independent set in satisfying both conditions (i) and (ii). □
Figure 3 presents the generalized corona
with the
-kernel indicated by the green color.
4. -Kernels in the G-Join of Graphs
In this section, we consider the problem of the existence and the number of -kernels in the G-join of graphs. We will show that the existence of a -kernel in the G-join of graphs does not require the existence of a -kernel in all their factors.
Problems of the existence of different kinds of kernels in
D-join of digraphs were considered in [
29,
30,
31].
We provide the definition of the G-join of graphs. Let G be a graph such that , and let be a sequence of arbitrary non-empty graphs, where , , and . The G-join of the graph G and the sequence is the graph such that and and
.
Figure 4 shows the graph
.
Some well-known graph products are specific cases of G-join. If and , then we obtain a join of two graphs . If for all , then is a composition of two graphs G and H. To obtain the next special case of G-join, let and . If for all and , , then is a duplication of the set X. In particular, if , then is a duplication of the vertex .
At first, we consider the case where all graphs from the sequence are nontrivial. The next theorem presents the complete characterization of the G-join of graphs having -kernels when no graph from the sequence is trivial.
Theorem 6. Let G be an arbitrary connected graph with vertices and be a sequence of n nontrivial graphs. The graph has a -kernel if, and only if, there exists a maximal independent set of the graph G such that for all the graph has a -kernel.
Proof. Let us assume that the graph has a -kernel . We will show that in the set : there exists
such that
is a maximal independent set. Let . From the independence of the set , it follows that the set J is independent. To prove that J is a maximal independent set, we will show that J is dominating. Let , , then . Hence, every vertex , is adjacent to a vertex , , , thus . Therefore, the set J is dominating. This means that J is a kernel, so it is a maximal independent set. Since has a -kernel , every graph , must have a -kernel . By the assumption, graphs , are nontrivial, hence .
Conversely, let us assume that the set J is a maximal independent set of a graph G and let . Suppose that the set , is a -kernel of a graph . Since the graph , is nontrivial, . We will show that the set is a -kernel of a graph . It is easy to check that is independent. Let for , . If , then for some . Hence, , otherwise, . Therefore, for every vertex , there exist at least two adjacent vertices in the set . From the definition of the graph , it follows that the vertex is 2-dominated by the set . Let . Since J is a maximal independent set of a graph G, there exists the vertex from the set J adjacent to . From the assumption that graphs , are nontrivial, we obtain that there exist two vertices from the set adjacent to . Hence, is a -kernel of a graph , which ends the proof. □
By the construction of a -kernel in the proof above, we obtain the value of parameters in the graph .
Corollary 4. Let G be an arbitrary connected graph with vertices and be a sequence of n nontrivial graphs having -kernel. Let , be the family of maximal independent sets of a graph G and let , . Then,
- 1.
,
- 2.
,
- 3.
Finally, we consider a more general concept. Suppose that graphs from the sequence are arbitrary.
Theorem 7. Let G be an arbitrary connected graph with vertices and be a sequence of n arbitrary non-empty graphs. The graph has a -kernel if, and only if, there exists a maximal independent set of the graph G such that , has a -kernel. Moreover, if for some , , then every vertex adjacent to in a graph G is 2-dominated by the set J.
Proof. If all graphs , are nontrivial, then we prove analogously as Theorem 6. Suppose that , . Assume that the graph has a -kernel . Let
: there exists
such that and let . If , then we prove analogously as Theorem 6. Suppose that and let . Let us consider the vertex , . Since is a -kernel of the graph , every vertex , is 2-dominated. This means that there exists at least one vertex , , , adjacent to in the graph . Thus . Since , the vertex . Hence, every vertex adjacent to in the graph G is 2-dominated by the set J.
Conversely, let J be a maximal independent set of a graph G and let . Assume that the set , is a -kernel of the graph . If , then we prove analogously as Theorem 6. Let . Suppose that every vertex adjacent to , is 2-dominated by the set J in the graph G. We will show that the set is a -kernel of the graph . From the definition of G-join, it follows that is independent. Let for , . If , then for some . Then, , otherwise, . Thus, for all vertices there exist at least two vertices in the set adjacent to in a graph G. Then, we obtain that the vertex is 2-dominated by . Let . Since J is a maximal independent set of the graph G, there exists at least one vertex , adjacent to . If , then we obtain that there exist two vertices from adjacent to . If , then and there exists at least one vertex , , adjacent to in the graph G. This means that there exist two vertices from the set adjacent to in the graph . Hence, is a -kernel of the graph , which ends the proof. □
From Theorem 7, we obtain direct corollaries, concerning specific cases of the G-join.
Corollary 5. Let be nontrivial graphs. The composition has a -kernel if, and only if, H has -kernel.
Corollary 6. The join has a -kernel if, and only if, at least one of graphs has a -kernel J such that .
Corollary 7. Let . The duplication has a -kernel if, and only if, there exist a maximal independent set such that if for some , then every vertex adjacent to in G is 2-dominated by the set J.
An example of a
G-join with
-kernel is shown in
Figure 5.
Finally, let us indicate that the problem of the existence of
-kernels in the
G-join for
has been solved by Michalski and Włoch in [
25]. They also proved some results concerning parameters related to
-kernels in this product. In
Figure 6, we present an example of a
-kernel in the graph
.