[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Next Article in Journal
A Study on Nonlinear Dynamic Response of the Large-Span Roof Structure with Suspended Substructure
Next Article in Special Issue
The Values of the Periodic Zeta-Function at the Nontrivial Zeros of Riemann’s Zeta-Function
Previous Article in Journal
Bounds for the Differences between Arithmetic and Geometric Means and Their Applications to Inequalities
Previous Article in Special Issue
Riemann Hypothesis and Random Walks: The Zeta Case
You seem to have javascript disabled. Please note that many of the page functionalities won't work as expected without javascript enabled.
 
 
Font Type:
Arial Georgia Verdana
Font Size:
Aa Aa Aa
Line Spacing:
Column Width:
Background:
Article

On Independent Secondary Dominating Sets in Generalized Graph Products

by
Adrian Michalski
*,† and
Paweł Bednarz
The Faculty of Mathematics and Applied Physics, Rzeszów University of Technology, al. Powstańców Warszawy 12, 35-959 Rzeszów, Poland
*
Author to whom correspondence should be addressed.
These authors contributed equally to this work.
Symmetry 2021, 13(12), 2399; https://doi.org/10.3390/sym13122399
Submission received: 12 November 2021 / Revised: 9 December 2021 / Accepted: 10 December 2021 / Published: 12 December 2021
(This article belongs to the Special Issue Number Theory and Discrete Mathematics)
Figure 1
<p>An example of the generalized corona <math display="inline"><semantics> <mrow> <msub> <mi>C</mi> <mn>6</mn> </msub> <mo>∘</mo> <mrow> <mo>(</mo> <mo>(</mo> <msub> <mi>P</mi> <mn>5</mn> </msub> <mo>,</mo> <msub> <mi>K</mi> <mn>1</mn> </msub> <mo>,</mo> <mo>∅</mo> <mo>,</mo> <msub> <mi>N</mi> <mn>3</mn> </msub> <mo>,</mo> <msub> <mi>C</mi> <mn>4</mn> </msub> <mo>,</mo> <msub> <mi>K</mi> <mn>4</mn> </msub> <mo>)</mo> </mrow> <mrow> <mo>)</mo> </mrow> </mrow> </semantics></math>.</p> ">
Figure 2
<p>An example of a <math display="inline"><semantics> <mrow> <mo>(</mo> <mn>1</mn> <mo>,</mo> <mn>1</mn> <mo>)</mo> </mrow> </semantics></math>-kernel in <math display="inline"><semantics> <mrow> <msub> <mi>P</mi> <mn>6</mn> </msub> <mo>∘</mo> <mrow> <mo>(</mo> <msub> <mi>P</mi> <mn>5</mn> </msub> <mo>,</mo> <msub> <mi>K</mi> <mn>1</mn> </msub> <mo>,</mo> <mo>∅</mo> <mo>,</mo> <msub> <mi>K</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>C</mi> <mn>4</mn> </msub> <mo>,</mo> <mrow> <mo>(</mo> <msub> <mi>K</mi> <mn>1</mn> </msub> <mo>∪</mo> <msub> <mi>C</mi> <mn>4</mn> </msub> <mo>)</mo> </mrow> <mo>)</mo> </mrow> </mrow> </semantics></math>.</p> ">
Figure 3
<p>An example of <math display="inline"><semantics> <mrow> <mo>(</mo> <mn>1</mn> <mo>,</mo> <mn>2</mn> <mo>)</mo> </mrow> </semantics></math>-kernel in <math display="inline"><semantics> <mrow> <msub> <mi>P</mi> <mn>6</mn> </msub> <mo>∘</mo> <mrow> <mo>(</mo> <msub> <mi>P</mi> <mn>4</mn> </msub> <mo>,</mo> <msub> <mi>K</mi> <mn>1</mn> </msub> <mo>,</mo> <mo>∅</mo> <mo>,</mo> <msub> <mi>K</mi> <mn>4</mn> </msub> <mo>,</mo> <msub> <mi>C</mi> <mn>4</mn> </msub> <mo>,</mo> <mrow> <mo>(</mo> <msub> <mi>P</mi> <mn>2</mn> </msub> <mo>∪</mo> <msub> <mi>C</mi> <mn>3</mn> </msub> <mo>)</mo> </mrow> <mo>)</mo> </mrow> </mrow> </semantics></math>.</p> ">
Figure 4
<p>An example of the graph <math display="inline"><semantics> <mrow> <msub> <mi>C</mi> <mn>6</mn> </msub> <mrow> <mo>(</mo> <mrow> <mo>(</mo> <msub> <mi>P</mi> <mn>5</mn> </msub> <mo>,</mo> <msub> <mi>K</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>P</mi> <mn>2</mn> </msub> <mo>,</mo> <msub> <mi>N</mi> <mn>3</mn> </msub> <mo>,</mo> <msub> <mi>C</mi> <mn>4</mn> </msub> <mo>,</mo> <msub> <mi>K</mi> <mn>4</mn> </msub> <mo>)</mo> </mrow> <mo>)</mo> </mrow> </mrow> </semantics></math>.</p> ">
Figure 5
<p>An example of <math display="inline"><semantics> <mrow> <mo>(</mo> <mn>1</mn> <mo>,</mo> <mn>1</mn> <mo>)</mo> </mrow> </semantics></math>-kernel in <math display="inline"><semantics> <mrow> <msub> <mi>P</mi> <mn>6</mn> </msub> <mrow> <mo>(</mo> <mrow> <mo>(</mo> <msub> <mi>P</mi> <mn>3</mn> </msub> <mo>,</mo> <msub> <mi>K</mi> <mn>4</mn> </msub> <mo>,</mo> <msub> <mi>N</mi> <mn>2</mn> </msub> <mo>,</mo> <msub> <mi>P</mi> <mn>4</mn> </msub> <mo>,</mo> <msub> <mi>P</mi> <mn>3</mn> </msub> <mo>,</mo> <msub> <mi>K</mi> <mn>1</mn> </msub> <mo>)</mo> </mrow> <mo>)</mo> </mrow> </mrow> </semantics></math>.</p> ">
Figure 6
<p>An example of <math display="inline"><semantics> <mrow> <mo>(</mo> <mn>1</mn> <mo>,</mo> <mn>2</mn> <mo>)</mo> </mrow> </semantics></math>-kernel in <math display="inline"><semantics> <mrow> <msub> <mi>P</mi> <mn>6</mn> </msub> <mrow> <mo>(</mo> <mrow> <mo>(</mo> <msub> <mi>P</mi> <mn>3</mn> </msub> <mo>,</mo> <msub> <mi>K</mi> <mn>4</mn> </msub> <mo>,</mo> <msub> <mi>N</mi> <mn>2</mn> </msub> <mo>,</mo> <msub> <mi>P</mi> <mn>4</mn> </msub> <mo>,</mo> <msub> <mi>P</mi> <mn>3</mn> </msub> <mo>,</mo> <msub> <mi>K</mi> <mn>1</mn> </msub> <mo>)</mo> </mrow> <mo>)</mo> </mrow> </mrow> </semantics></math>.</p> ">
Versions Notes

Abstract

:
In 2008, Hedetniemi et al. introduced ( 1 , k ) -domination in graphs. The research on this concept was extended to the problem of existence of independent ( 1 , k ) -dominating sets, which is an NP -complete problem. In this paper, we consider independent ( 1 , 1 ) - and ( 1 , 2 ) -dominating sets, which we name as ( 1 , 1 ) -kernels and ( 1 , 2 ) -kernels, respectively. We obtain a complete characterization of generalized corona of graphs and G-join of graphs, which have such kernels. Moreover, we determine some graph parameters related to these sets, such as the number and the cardinality. In general, graph products considered in this paper have an asymmetric structure, contrary to other many well-known graph products (Cartesian, tensor, strong).

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 G = ( , ) is an empty graph and G is trivial if it is empty or | V ( G ) | = 1 . If | V ( G ) | 2 , then G is nontrivial. We say that a subset D V ( G ) 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 S V ( G ) 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 α ( G ) , whereas minimum cardinality of a maximal independent set (or, equivalently, an independent dominating set) in G we denote by i ( G ) . By σ ( G ) 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, ( k , l ) -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 p 1 , a subset D V ( G ) is called a p-dominating set of G if every vertex from V ( G ) \ D has at least p neighbors in D. For p = 1 , we get the classical definition of the dominating set. If p = 2 , 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 D V ( G ) is ( 1 , k ) -dominating if for every x V ( G ) \ D there exist distinct vertices v , w D such that x v E ( G ) and d G ( x , w ) k . By combining this type of domination with independence, we obtain ( 1 , k ) -kernels, i.e., subsets, which are independent and ( 1 , k ) -dominating. Let us observe that ( 1 , 1 ) -kernels are equivalent to 2-dominating kernels. In general, the problem of the existence of secondary dominating kernels is NP -complete (see [19,20]). Some problems concerning ( 1 , 1 ) -kernels in trees, graph products, and generalized Petersen graphs were considered in [20,21,22,23,24], while ( 1 , 2 ) -kernels were studied, among others, in [19,25].
In our considerations we will use the following notation:
  • σ ( 1 , k ) ( G ) the number of all ( 1 , k ) -kernels in G.
  • j ( 1 , k ) ( G ) the lower ( 1 , k ) -kernel number, i.e. minimum cardinality of a ( 1 , k ) -kernel in G.
  • J ( 1 , k ) ( G ) the upper ( 1 , k ) -kernel number, i.e. maximum cardinality of a ( 1 , k ) -kernel in G.
This paper concerns the problem of the existence and the number of ( 1 , 1 ) -kernels and ( 1 , 2 ) -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 ( 1 , 1 ) -kernels and ( 1 , 2 ) -kernels as well as determining general formulas for parameters σ ( 1 , k ) , j ( 1 , k ) , and J ( 1 , k ) in the generalized corona.
  • Giving complete characterization of the G-join with ( 1 , 1 ) -kernels and applying them to describe those kernels in other graph operations such as the join, the composition, and the duplication of vertices.

2. ( 1 , 1 ) -Kernels in the Generalized Corona of Graphs

In this section, we consider the problem of the existence and the number of ( 1 , 1 ) -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 V ( G ) = { x 1 , x 2 , , x n } , n 1 and let h n = ( H i ) i I be a sequence of arbitrary graphs, where I = { 1 , 2 , , n } is the set of indices. The generalized corona of a graph G and the sequence h n is the graph G h n such that V ( G h n ) = V ( G ) i = 1 n V ( H i ) and E ( G h n ) = E ( G ) i = 1 n E ( H i ) i = 1 n { x i y : y V ( H i ) } .
Figure 1 shows the generalized corona C 6 ( P 5 , K 1 , , N 3 , C 4 , K 4 ) ) .
Now, we give necessary and sufficient conditions for the existence of ( 1 , 1 ) -kernels in the generalized corona of graphs, where all of the graphs from the sequence h n are nontrivial.
Theorem 1.
Let G be an arbitrary graph with n 1 vertices and h n = ( H i ) i I be a sequence of n nontrivial graphs. The graph G h n has a ( 1 , 1 ) -kernel if, and only if, all graphs H i , i I have a ( 1 , 1 ) -kernel.
Proof. 
Assume that graphs H i , i I have a ( 1 , 1 ) -kernel J i . Since graphs H i are nontrivial, | V ( H i ) | 2 . Thus, | J i | 2 . We will show that for an arbitrary graph G of order n 1 , the set J = i = 1 n J i is a ( 1 , 1 ) -kernel of a graph G h n . From the definition of the generalized corona of graphs it follows that J is an independent set. Since | J i | 2 , every vertex of a graph G has at least two neighbors in the set J i . Hence, J is a ( 1 , 1 ) -kernel of a graph G h n .
Conversely, let us assume that a certain graph G h n , n 1 has a ( 1 , 1 ) -kernel J. We will show that J V ( G ) = . Let x s V ( G ) , 1 s n , and suppose by the contrary that x s J . Then, V ( H s ) J = . Since | V ( H s ) | 2 , the set J is not 2-dominating, a contradiction with the assumption that J is a ( 1 , 1 ) -kernel. Hence, J V ( G ) = . Since the graph G h n has a ( 1 , 1 ) -kernel J and J V ( G ) = , graphs H i , i I must have a ( 1 , 1 ) -kernel J i . Moreover, every vertex x i V ( G ) has at least two neighbors in the set J i . Therefore, | J i | 2 , and hence | V ( H i ) | 2 , which ends the proof. □
Based on the proof of Theorem 1, the following corollary is obtained. It concerns the number of ( 1 , 1 ) -kernels in the generalized corona of graphs as well as the lower and upper ( 1 , 1 ) -kernel numbers.
Corollary 1.
Let G be an arbitrary graph with n 1 vertices and h n = ( H i ) i I be a sequence of n nontrivial graphs. If graphs H i have a ( 1 , 1 ) -kernel, then
1.
σ ( 1 , 1 ) ( G h n ) = i = 1 n σ ( 1 , 1 ) ( H i ) ,
2.
j ( 1 , 1 ) ( G h n ) = i = 1 n j ( 1 , 1 ) ( H i ) ,
3.
J ( 1 , 1 ) ( G h n ) = i = 1 n J ( 1 , 1 ) ( H i ) .
Now, let us consider the case where graphs from the sequence h n are arbitrary. Let h n = ( H i ) i I be a sequence of arbitrary graphs. In particular, graphs from the sequence h n can be trivial or empty. Let I = I 0 I 1 I 2 , where I 0 = { j I : | V ( H j ) | = 0 } , I 1 = { t I : | V ( H t ) | = 1 } , I 2 = { r I : | V ( H r ) | 2 } . We give the complete characterization of the generalized corona of graphs with a ( 1 , 1 ) -kernel.
Theorem 2.
Let G be an arbitrary graph with n 1 vertices and h n = ( H i ) i I be a sequence of n arbitrary graphs. The graph G h n has a ( 1 , 1 ) -kernel if, and only if, each graph H r , r I 2 has a ( 1 , 1 ) -kernel and the subgraph G h n \ r I 2 V ( H r ) { x r } has a ( 1 , 1 ) -kernel.
Proof. 
Let us assume that a certain graph G h n has a ( 1 , 1 ) -kernel J. Then, each graph H r , r I 2 must have a ( 1 , 1 ) -kernel J r to 2-dominate vertices from the set V ( H r ) \ J r . Since N G h n [ J r ] = V ( H r ) { x r } , r I 2 , the subgraph G h n \ r I 2 V ( H r ) { x r } must have a ( 1 , 1 ) -kernel.
Conversely, let us assume that each graph H r , r I 2 has a ( 1 , 1 ) -kernel J r and the subgraph G h n \ r I 2 H r { x r } has a ( 1 , 1 ) -kernel J * . We will show that the set J = J * r I 2 J r is a ( 1 , 1 ) -kernel of the graph G h n . 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 v V ( G h n ) \ J . If v V ( H r ) { x r } , r I 2 , then the vertex v is 2-dominated by the set J r . If v k I 0 I 1 { x k } , then the vertex v has at least two neighbors in the set J * . This means that the set J is a ( 1 , 1 ) -kernel of the graph G h n , which ends the proof. □
By the construction of ( 1 , 1 ) -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 n 1 vertices and h n = ( H i ) i I be a sequence of n arbitrary graphs and let G 1 G h n \ r I 2 V ( H r ) { x r } . If the graph G h n has a ( 1 , 1 ) -kernel, then
1.
σ ( 1 , 1 ) ( G h n ) = σ ( 1 , 1 ) G 1 · r I 2 σ ( 1 , 1 ) ( H r ) ,
2.
j ( 1 , 1 ) ( G h n ) = j ( 1 , 1 ) G 1 + r I 2 j ( 1 , 1 ) ( H r ) ,
3.
J ( 1 , 1 ) ( G h n ) = J ( 1 , 1 ) G 1 + r I 2 J ( 1 , 1 ) ( H r ) .
Finally, we give another complete characterization of the generalized corona of arbitrary graphs.
Theorem 3.
Let G be an arbitrary graph with n 1 vertices and h n = ( H i ) i I be a sequence of n arbitrary graphs. The graph G h n has a ( 1 , 1 ) -kernel if, and only if, the following conditions hold:
(i) 
Each graph H r , r I 2 has a ( 1 , 1 ) -kernel.
(ii) 
The subgraph induced by the set { x j : j I 0 } has a ( 1 , 1 ) -kernel J * .
(iii) 
For t I 1 there exists i I 0 such that x t x i E ( G ) and x i J * .
Proof. 
Let us assume that a certain graph G h n has a ( 1 , 1 ) -kernel J. Then, each graph H r , r I 2 must have a ( 1 , 1 ) -kernel J r to 2-dominate vertices from the set V ( H r ) \ J r . Thus, the condition (i) holds. We will show that the subgraph induced by the set { x j : j I 0 } has a ( 1 , 1 ) -kernel. If x i V ( G ) J , then i I 0 . Otherwise, the set J is not independent. Let J * = V ( G ) J . Since J is a ( 1 , 1 ) -kernel of the graph G h n , the set J * is a ( 1 , 1 ) -kernel of the subgraph induced by the set { x j : j I 0 } . Hence, the condition (ii) holds. For all t I 1 , we have | N G h n ( x t ) ( J \ V ( G ) ) | = 1 . To 2-dominate vertices x t , t I 1 there must exist x i J * , i I 0 such that x i x t E ( G ) . Thus, the condition (iii) holds.
Conversely, let us assume that conditions (i)(iii) hold. We will show that the graph G h n has a ( 1 , 1 ) -kernel J = r I 2 J r t I 1 V ( H t ) J * , where J r is a ( 1 , 1 ) -kernel of the graph H r for r I 2 and J * is a ( 1 , 1 ) -kernel of the subgraph induced by the set { x j : j I 0 } . The independence of the set J follows from the definition of G h n . Thus, it is sufficient to show that the set J is 2-dominating. Let v V ( G h n ) \ J . If v V ( H r ) { x r } , r I 2 , then the vertex v is 2-dominated by the set J r . If v = x t , t I 1 , then the vertex v is 2-dominated by the set V ( H t ) J * . If v = x j , j I 0 , then the vertex v is 2-dominated by the set J * . Hence, the set J is a ( 1 , 1 ) -kernel of the graph G h n , which ends the proof. □
Figure 2 shows the generalized corona P 6 ( P 5 , K 1 , , K 1 , C 4 , ( K 1 C 4 ) ) and an example of a ( 1 , 1 ) -kernel in this graph.

3. ( 1 , 2 ) -Kernels in the Generalized Corona of Graphs

In this section, we study the existence of ( 1 , 2 ) -kernels in the generalized corona. Let x V ( G ) . The set N G k ( x ) = { v V ( G ) : d G ( x , v ) k } we will refer to as the k-th weak neighborhood of the vertex x in the graph G. In particular, the set N G 2 ( x ) we refer to as the second weak neighborhood of x.
Let I = { 1 , 2 , , n } be the set of indices. We denote as follows: by I 0 , the set { j I : H j = } and by I K , the set { j I : H j K n , n 2 } . For simplicity, the subgraph of G induced by the set { x j : j I 0 } , we denote by G [ I 0 ] .
Let us begin with proving lemmas, which will be helpful in our next considerations concerning the complete characterization of generalized corona with ( 1 , 2 ) -kernels.
Lemma 1.
Let J be a ( 1 , 2 ) -kernel in the generalized corona G h n . If i I \ I 0 , then x i J .
Proof. 
Let J be a ( 1 , 2 ) -kernel. By contradiction, let us suppose that i I \ I 0 and x i J . It follows that no vertex of the graph H i belongs to J. Moreover, for any j I such that x i x j E ( G ) , we have x j J . This means that for any vertex y V ( H i ) , we have N G h n 2 ( y ) J = { x i } , which means that y is not ( 1 , 2 ) -dominated by J, a contradiction. □
Lemma 2.
Let G h n have a ( 1 , 2 ) -kernel. If i I K , then there exists j I 0 such that x i x j E ( G ) .
Proof. 
Let G h n have a ( 1 , 2 ) -kernel J. For the sake of contradiction, let us assume that for some i I K , there is no j I 0 such that x i x j E ( G ) . By Lemma 1, we know that x i J . Moreover, any other neighbor of x i in G also does not belong to J. This means that the intersection of sets V ( H i ) and J consists of unique vertex y , which dominates all other vertices of V ( H i ) and the vertex x i , but it implies that for all vertices y V ( H i ) \ { y } , we have N G h n 2 ( y ) J = { y } , which means they are not ( 1 , 2 ) -dominated, a contradiction. □
Now, we are ready to present necessary and sufficient conditions for a generalized corona of graphs to have a ( 1 , 2 ) -kernel.
Theorem 4.
Let G be an arbitrary connected, nontrivial graph, h n = ( H i ) i I be a sequence of graphs such that I 0 = . The generalized corona G h n has a ( 1 , 2 ) -kernel if, and only if, I K = .
Proof. 
First, we prove the sufficient condition. Let us assume that I K = , i.e., for any i I , the graph H i is not isomorphic to K n , n 2 . In each graph H i we take an independent set of maximum cardinality and denote it by J i . Let us consider the set J = i = 1 n J i . Clearly, J is independent in G h n . We show that it is ( 1 , 2 ) -dominating. Let v V ( G h n ) \ J . First, let v V ( G ) ; this means v = x i for some i I . If | J i | 2 , then the x i is ( 1 , 1 ) -dominated by J i . If | J i | = 1 , then x i is dominated by J i and there exists a path x i x j J j of length 2. Now, we assume that v belongs to V ( H i ) for some i I . The set J i is dominating in H i and has at least two vertices, say y 1 , y 2 . This means v is dominated by at least one of them, say y 1 and, by the definition of generalized corona, there exists a path v x i y 2 . Hence, J is ( 1 , 2 ) -dominating.
To prove the necessary condition, let us suppose that G h n has a ( 1 , 2 ) -kernel J. For the sake of contradiction, let I K . By Lemma 2, it means that I 0 . A contradiction with the assumption that I 0 = means that I K = . □
From the proof of Theorem 4, we may conclude a corollary concerning the number of all ( 1 , 2 ) -kernels as well as lower and upper ( 1 , 2 ) -kernel numbers in some cases of generalized corona.
Corollary 3.
Let G be an arbitrary, connected, nontrivial graph with n vertices and h n = ( H i ) i I be a sequence of n arbitrary graphs such that i ( H i ) 2 for all i I .
1.
σ ( 1 , 2 ) ( G h n ) = i = 1 n σ ( H i ) ,
2.
j ( 1 , 2 ) ( G h n ) = i = 1 n i ( H i ) ,
3.
J ( 1 , 2 ) ( G h n ) = i = 1 n α ( H i ) .
Now, we consider a more general concept, i.e., we allow that graphs from the sequence h n can be empty.
Theorem 5.
Let G be an arbitrary connected non-empty graph, h n = ( H i ) i I be a sequence of graphs, and I 0 . The generalized corona G h n has a ( 1 , 2 ) -kernel if, and only if, the subgraph G [ I 0 ] has a maximal independent set S such that the following conditions hold:
(i) 
If i I K , then there exists x j S such that x i x j E ( G ) and
(ii) 
For every vertex x k V ( G [ I 0 ] ) \ S at least one of the following conditions is satisfied:
(a) 
There exists l I \ I 0 such that x k x l E ( G ) .
(b) 
x k is ( 1 , 2 ) -dominated by the set S.
Proof. 
First, we will prove the sufficient condition. Let us assume that the subgraph G [ I 0 ] has a maximal independent set S such that conditions (i) and (ii) are satisfied. We will show that G h n has a ( 1 , 2 ) -kernel. If i I 0 , then in the graph H i we take any independent set of the maximum cardinality and denote it by J i . Let J = i I \ I 0 J i S . It is easy to see that J is independent. We will show it is ( 1 , 2 ) -dominating. Let us divide all vertices lying outside J into four cases.
First, let i I be such that the graph H i has at least two vertices and is not complete. Then, x i V ( G ) \ J is ( 1 , 1 ) -dominated by J i and for all y V ( H i ) \ J i , we have N G h n 2 ( y ) J i 2 .
Second, let i I be such that H i K 1 . If the vertex x i has a neighbor x l V ( G ) such that l I \ I 0 , then N G h n 2 ( x i ) ( J i J l ) 2 . Therefore, let us suppose that for all j such that x j x i E ( G ) , we have j I 0 . If there exists j S such that x i x j E ( G ) , then x i is ( 1 , 1 ) -dominated by the set J i S . Otherwise, by maximality of S in G [ I 0 ] we obtain N G h n 2 ( x i ) ( J i S ) 2 . Hence, x i is ( 1 , 2 ) -dominated by J.
Third, let i I K . Then, by the condition (i), the vertex x i is ( 1 , 1 ) -dominated by the set J i S and for all y V ( H i ) \ J i , we have N G h n 2 ( y ) ( J i S ) 2 .
Fourth, let i I 0 . Then, by maximality of S in G [ I 0 ] and the condition (ii), we have N G h n 2 ( x i ) S 2 or N G h n 2 ( x i ) ( S J l ) 2 , where l I \ I 0 and x i x l E ( G ) .
This means that the set J is ( 1 , 2 ) -dominating in G h n , hence it is a ( 1 , 2 ) -kernel.
Now, we prove the necessary condition. Let us suppose that G h n has a ( 1 , 2 ) -kernel J. For the sake of contradiction, let us assume that in the subgraph G [ I 0 ] , no maximal independent set satisfies both conditions (i) and (ii). This means that for every maximal independent set S of G [ I 0 ] :
  • There exists H i K n , n 2 such that x i has no neighbor in S or
  • There exists a vertex x k V ( G [ I 0 ] ) \ S , which is neither ( 1 , 2 ) -dominated by S nor has a neighbor x l , l I \ I 0 .
Since the intersection of J and V ( G [ I 0 ] ) must be a maximal independent set in G [ I 0 ] , we obtain that we always find at least one vertex z V ( H i ) \ J , i I K , which is not ( 1 , 2 ) -dominated by J, or a vertex x k V ( G [ I 0 ] ) \ J , which is not ( 1 , 2 ) -dominated by J. This is a contradiction with the fact that J is a ( 1 , 2 ) -kernel. Hence, there must exist a maximal independent set in G [ I 0 ] satisfying both conditions (i) and (ii). □
Figure 3 presents the generalized corona P 6 ( P 4 , K 1 , , K 4 , C 4 , ( P 2 C 3 ) ) with the ( 1 , 2 ) -kernel indicated by the green color.

4. ( 1 , 1 ) -Kernels in the G-Join of Graphs

In this section, we consider the problem of the existence and the number of ( 1 , 1 ) -kernels in the G-join of graphs. We will show that the existence of a ( 1 , 1 ) -kernel in the G-join of graphs does not require the existence of a ( 1 , 1 ) -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 V ( G ) = { x 1 , x 2 , , x n } , n 2 and let h n = H i i I be a sequence of arbitrary non-empty graphs, where V ( H i ) = { y 1 i , y 2 i , , y p i i } , p i 1 , and I = { 1 , 2 , , n } . The G-join of the graph G and the sequence h n is the graph G [ h n ] such that V ( G [ h n ] ) = i = 1 n { x i } × V ( H i ) and E ( G [ h n ] ) = { ( x s , y j s ) ( x q , y t q ) ; x s = x q and y j s y t q E ( H s ) o r x s x q E ( G ) } .
Figure 4 shows the graph C 6 [ ( P 5 , K 1 , P 2 , N 3 , C 4 , K 4 ) ] .
Some well-known graph products are specific cases of G-join. If G P 2 and h n = ( H 1 , H 2 ) , then we obtain a join of two graphs H 1 + H 2 . If H i H for all i I , then G [ h n ] is a composition of two graphs G and H. To obtain the next special case of G-join, let X V ( G ) and X = { x i : i I * I } . If H j K 1 for all j I \ I * and H i N 2 , i I * , then G [ h n ] is a duplication of the set X. In particular, if | I * | = 1 , then G [ h n ] is a duplication of the vertex x i .
At first, we consider the case where all graphs from the sequence h n are nontrivial. The next theorem presents the complete characterization of the G-join of graphs having ( 1 , 1 ) -kernels when no graph from the sequence h n is trivial.
Theorem 6.
Let G be an arbitrary connected graph with n 1 vertices and h n = ( H i ) i I be a sequence of n nontrivial graphs. The graph G [ h n ] has a ( 1 , 1 ) -kernel if, and only if, there exists a maximal independent set J = { x i : i I I } of the graph G such that for all i I the graph H i has a ( 1 , 1 ) -kernel.
Proof. 
Let us assume that the graph G [ h n ] has a ( 1 , 1 ) -kernel J * . We will show that in the set J = { x i V ( G ) : there exists y k i V ( H i ) such that ( x i , y k i ) J * } is a maximal independent set. Let I = { i I : x i J } . From the independence of the set J * , 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 x t V ( G ) \ J , t I \ I , then { x t } × V ( H t ) J * = . Hence, every vertex ( x t , y j t ) J * , 1 j p t is adjacent to a vertex ( x s , y r s ) J * , s I , 1 r p s , thus x t x s E ( G ) . Therefore, the set J is dominating. This means that J is a kernel, so it is a maximal independent set. Since G [ h n ] has a ( 1 , 1 ) -kernel J * , every graph H i , i I must have a ( 1 , 1 ) -kernel J i . By the assumption, graphs H i , i I are nontrivial, hence | J i | 2 .
Conversely, let us assume that the set J is a maximal independent set of a graph G and let I = { i I : x i J } . Suppose that the set J i , i I is a ( 1 , 1 ) -kernel of a graph H i . Since the graph H i , i I is nontrivial, | J i | 2 . We will show that the set J * = i I { x i } × J i is a ( 1 , 1 ) -kernel of a graph G [ h n ] . It is easy to check that J * is independent. Let ( x s , y r s ) V ( G [ h n ] ) \ J * for 1 s n , 1 r p s . If x s J , then x s = x k for some k I . Hence, y r s J k , otherwise, ( x s , y r s ) J * . Therefore, for every vertex y r s J k , there exist at least two adjacent vertices in the set J k . From the definition of the graph G [ h n ] , it follows that the vertex ( x s , y r s ) is 2-dominated by the set J * . Let x s J . Since J is a maximal independent set of a graph G, there exists the vertex from the set J adjacent to x s . From the assumption that graphs H i , i I are nontrivial, we obtain that there exist two vertices from the set J * adjacent to ( x s , y r s ) . Hence, J * is a ( 1 , 1 ) -kernel of a graph G [ h n ] , which ends the proof. □
By the construction of a ( 1 , 1 ) -kernel in the proof above, we obtain the value of parameters σ ( 1 , 1 ) , j ( 1 , 1 ) , J ( 1 , 1 ) in the graph G [ h n ] .
Corollary 4.
Let G be an arbitrary connected graph with n 1 vertices and h n = ( H i ) i I be a sequence of n nontrivial graphs having ( 1 , 1 ) -kernel. Let J = { J 1 , J 2 , , J t } , t 1 be the family of maximal independent sets of a graph G and let J k = { x i : i I k I } , k = 1 , 2 , , t . Then,
1.
σ ( 1 , 1 ) ( G [ h n ] ) = k = 1 t i I k σ ( H i ) ,
2.
j ( 1 , 1 ) ( G [ h n ] ) = min i I k j ( H i ) : k = 1 , 2 , , t ,
3.
J ( 1 , 1 ) ( G [ h n ] ) = max i I k J ( H i ) : k = 1 , 2 , , t .
Finally, we consider a more general concept. Suppose that graphs from the sequence h n are arbitrary.
Theorem 7.
Let G be an arbitrary connected graph with n 1 vertices and h n = ( H i ) i I be a sequence of n arbitrary non-empty graphs. The graph G [ h n ] has a ( 1 , 1 ) -kernel if, and only if, there exists a maximal independent set J = { x i : i I * I } of the graph G such that H i , i I * has a ( 1 , 1 ) -kernel. Moreover, if for some j I * , H j K 1 , then every vertex adjacent to x j in a graph G is 2-dominated by the set J.
Proof. 
If all graphs H i , i I are nontrivial, then we prove analogously as Theorem 6. Suppose that H m K 1 , m I ˜ I . Assume that the graph G [ h n ] has a ( 1 , 1 ) -kernel J * . Let J = { x i V ( G ) : there exists y k i V ( H i ) such that ( x i , y k i ) J * } and let I * = { i I : x i J } . If I ˜ I * = , then we prove analogously as Theorem 6. Suppose that I ˜ I * and let j I ˜ I * . Let us consider the vertex x s N G ( x j ) , 1 s n . Since J * is a ( 1 , 1 ) -kernel of the graph G [ h n ] , every vertex ( x s , y r s ) , 1 r p s is 2-dominated. This means that there exists at least one vertex ( x t , y u t ) , t I * , t j , 1 u p t adjacent to ( x s , y r s ) in the graph G [ h n ] . Thus x s x t E ( G ) . Since t I * , the vertex x t J . Hence, every vertex adjacent to x j 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 I * = { i I : x i J } . Assume that the set J i , i I * is a ( 1 , 1 ) -kernel of the graph H i . If I ˜ I * = , then we prove analogously as Theorem 6. Let I ˜ I * . Suppose that every vertex adjacent to x j , j I ˜ I * is 2-dominated by the set J in the graph G. We will show that the set J * = i I * { x i } × J i is a ( 1 , 1 ) -kernel of the graph G [ h n ] . From the definition of G-join, it follows that J * is independent. Let ( x s , y r s ) V ( G [ h n ] ) \ J * for 1 s n , 1 r p s . If x s J , then x s = x k for some k I * . Then, y r s J k , otherwise, ( x s , y r s ) J * . Thus, for all vertices y r s J k there exist at least two vertices in the set J k adjacent to y r s in a graph G. Then, we obtain that the vertex ( x s , y r s ) is 2-dominated by J * . Let x s J . Since J is a maximal independent set of the graph G, there exists at least one vertex x p J , p I * adjacent to x s . If | J p | 2 , then we obtain that there exist two vertices from J * adjacent to ( x s , y r s ) . If | J p | = 1 , then p I ˜ I * and there exists at least one vertex x t , t p , t I * adjacent to x s in the graph G. This means that there exist two vertices from the set J * adjacent to ( x s , y r s ) in the graph G [ h n ] . Hence, J * is a ( 1 , 1 ) -kernel of the graph G [ h n ] , which ends the proof. □
From Theorem 7, we obtain direct corollaries, concerning specific cases of the G-join.
Corollary 5.
Let G , H be nontrivial graphs. The composition G [ H ] has a ( 1 , 1 ) -kernel if, and only if, H has ( 1 , 1 ) -kernel.
Corollary 6.
The join H 1 + H 2 has a ( 1 , 1 ) -kernel if, and only if, at least one of graphs H 1 , H 2 has a ( 1 , 1 ) -kernel J such that | J | 2 .
Corollary 7.
Let X V ( G ) , X . The duplication G X has a ( 1 , 1 ) -kernel if, and only if, there exist a maximal independent set J = { x j : j I * I } such that if for some j I * , H j K 1 , then every vertex adjacent to x j in G is 2-dominated by the set J.
An example of a G-join with ( 1 , 1 ) -kernel is shown in Figure 5.
Finally, let us indicate that the problem of the existence of ( 1 , k ) -kernels in the G-join for k = 2 has been solved by Michalski and Włoch in [25]. They also proved some results concerning parameters related to ( 1 , 2 ) -kernels in this product. In Figure 6, we present an example of a ( 1 , 2 ) -kernel in the graph P 6 ( ( P 3 , K 4 , N 2 , P 4 , P 3 , K 1 ) ) .

5. Concluding Remarks

In this paper, we discussed the problem of the existence of ( 1 , 1 ) and ( 1 , 2 ) -kernels in generalized graph products, as well as determined parameters related to them. Together with results obtained in [25], this paper concludes the topic of ( 1 , 1 ) -kernels and ( 1 , 2 ) -kernels in generalized corona and G-join. Since the proven results are very general, they also solve the problem of the existence of secondary kernels in more specific cases, such as the composition of graphs, the duplication of the vertex, the classical join, and corona of two graphs. We showed that the asymmetry of these products is not an obstacle in finding complete characterizations. The main method used in proofs was thorough case analysis.
The problems analyzed in this paper are still open in a wide range of graph classes and we believe that the results presented here may be of major significance in exploring this field. One of the possibilities is obtaining complete characterizations of ( 1 , k ) -kernels in other graph products such as the Cartesian, tensor, and strong products. Some of these problems have been only partially solved in [19,21,23].

Author Contributions

All authors contributed equally to this work. All authors have read and agreed to the published version of the manuscript.

Funding

This research received no external funding.

Institutional Review Board Statement

Not applicable.

Informed Consent Statement

Not applicable.

Conflicts of Interest

The authors declare no conflict of interest.

References

  1. Diestel, R. Graph Theory, 3rd ed.; Springer: New York, NY, USA, 2005. [Google Scholar]
  2. Dettlaff, M.; Lemańska, M.; Rodríguez-Velázquez, J.A.; Zuazua, R. On the super domination number of lexicographic product graphs. Discret. Appl. Math. 2019, 263, 118–129. [Google Scholar] [CrossRef] [Green Version]
  3. Dettlaff, M.; Lemańska, M.; Topp, J.; Ziemann, R.; Żyliński, P. Certified domination. AKCE Int. J. Graphs Comb. 2020, 17, 86–97. [Google Scholar] [CrossRef]
  4. Erveš, R.; Žerovnik, J. On 2-Rainbow Domination Number of Generalized Petersen Graphs P (5k, k). Symmetry 2021, 13, 809. [Google Scholar] [CrossRef]
  5. Akram, M.; Sarwar, M.; Dudek, W.A. Graphs for the Analysis of Bipolar Fuzzy Information, Studies in Fuzziness and Soft Computing; Springer: Berlin/Heidelberg, Germany, 2021. [Google Scholar]
  6. Morgenstern, O.; Von Neumann, J. Theory of Games and Economic Behavior; Princeton University Press: Princeton, NJ, USA, 1944. [Google Scholar]
  7. Ore, O. Theory of graphs. Am. Math. Soc. Transl. 1962, 38, 206–212. [Google Scholar]
  8. Cockayne, E.J.; Hedetniemi, S.T. Towards a theory of domination in graphs. Networks 1977, 7, 247–261. [Google Scholar] [CrossRef]
  9. Włoch, I. Trees with extremal numbers of maximal independent sets including the set of leaves. Discret. Math. 2008, 308, 4768–4772. [Google Scholar] [CrossRef] [Green Version]
  10. Goddard, W.; Henning, M.A. Independent domination in graphs: A survey and recent results. Discret. Math 2013, 7, 839–854. [Google Scholar] [CrossRef]
  11. Galeana-Sánchez, H.; Hernández-Cruz, C. On the existence of (k,l)-kernels in infinite digraphs: A survey. Discuss. Math. Graph Theory 2014, 34, 431–466. [Google Scholar] [CrossRef]
  12. Kucharska, M.; Kwaśnik, M. On (k,l)-kernels of special superdigraphs of Pm and Cm. Discuss. Math. Graph Theory 2001, 21, 95–109. [Google Scholar] [CrossRef]
  13. Włoch, A.; Włoch, I. On (k,l)-kernels in the corona of digraphs. Int. J. Pure Appl. Math. 2009, 53, 571–582. [Google Scholar]
  14. Bange, D.W.; Barkauskas, A.E.; Slater, P.J. Efficient dominating sets in graphs. Appl. Discret. Math. 1988, 189, 189–199. [Google Scholar]
  15. Domke, G.S.; Hattingh, J.H.; Hedetniemi, S.T.; Laskar, R.C.; Markus, L.R. Restrained domination in graphs. Discret. Math. 1999, 203, 61–69. [Google Scholar] [CrossRef] [Green Version]
  16. Bednarz, U. Strong (1;1;2)-kernels in the corona of graphs and some realization problems. Iran. J. Sci. Technol. Trans. A Sci. 2020, 44, 401–406. [Google Scholar] [CrossRef] [Green Version]
  17. Fink, J.F.; Jacobson, M.S. n-domination in graphs. In Graph theory with Applications to Algorithms and Computer Science; John Wiley & Sons, Inc.: New York, NY, USA, 1985; pp. 283–300. [Google Scholar]
  18. Włoch, A. On 2-dominating kernels in graphs. Australas. J. Combin. 2012, 53, 273–284. [Google Scholar]
  19. Hedetniemi, S.M.; Hedetniemi, S.T.; Knisely, J.; Rall, D.F.; Haynes, T.W. Secondary domination in graphs. AKCE Int. J. Graphs Comb. 2008, 5, 103–115. [Google Scholar]
  20. Bednarz, P.; Hernández-Cruz, C.; Włoch, I. On the existence and the number of (2-d)-kernels in graphs. Ars Combin. 2015, 121, 341–351. [Google Scholar]
  21. Bednarz, P.; Włoch, I. On (2-d)-kernels in the cartesian product of graphs. Ann. Univ. Mariae Curie-Skłodowska Sect. A 2016, 70, 1–8. [Google Scholar] [CrossRef]
  22. Bednarz, P.; Włoch, I. An algorithm determining (2-d)-kernels in trees. Util. Math. 2017, 102, 215–222. [Google Scholar]
  23. Bednarz, P. On (2-d)-kernels in the tensor product of graphs. Symmetry 2021, 13, 230. [Google Scholar] [CrossRef]
  24. Bednarz, P.; Paja, N. On (2-d)-kernels in two generalizations of the Petersen graph. Symmetry 2021, 13, 1948. [Google Scholar] [CrossRef]
  25. Michalski, A.; Włoch, I. On the existence and the number of independent (1,2)-dominating sets in the G-join of graphs. Appl. Math. Comput. 2020, 377, 125155. [Google Scholar] [CrossRef]
  26. Frucht, R.; Harary, F. On the corona of two graphs. Aequationes Math. 1970, 4, 322–325. [Google Scholar] [CrossRef]
  27. Topp, J. Domination, Independence and Irredundance in Graphs; Dissertationes Mathematicae CCCXLII; Instytut Matematyczny PAN: Warszawa, Poland, 1995. [Google Scholar]
  28. Włoch, I. On kernels by monochromatic paths in the corona of digraphs. Cent. Eur. J. Math. 2008, 6, 537–542. [Google Scholar] [CrossRef]
  29. Galeana-Sánchez, H.; Sánchez-López, R. H-kernels in the D-join. Ars Combin. 2011, 98, 353–377. [Google Scholar]
  30. Kucharska, M. On (k,l)-kernel perfectness of special classes of digraphs. Discuss. Math. Graph Theory 2005, 25, 103–119. [Google Scholar] [CrossRef]
  31. Szumny, W.; Włoch, A.; Włoch, I. On the existence and on the number of (k,l)-kernels in the lexicographic product of graphs. Discret. Math. 2008, 308, 4616–4624. [Google Scholar] [CrossRef] [Green Version]
Figure 1. An example of the generalized corona C 6 ( ( P 5 , K 1 , , N 3 , C 4 , K 4 ) ) .
Figure 1. An example of the generalized corona C 6 ( ( P 5 , K 1 , , N 3 , C 4 , K 4 ) ) .
Symmetry 13 02399 g001
Figure 2. An example of a ( 1 , 1 ) -kernel in P 6 ( P 5 , K 1 , , K 1 , C 4 , ( K 1 C 4 ) ) .
Figure 2. An example of a ( 1 , 1 ) -kernel in P 6 ( P 5 , K 1 , , K 1 , C 4 , ( K 1 C 4 ) ) .
Symmetry 13 02399 g002
Figure 3. An example of ( 1 , 2 ) -kernel in P 6 ( P 4 , K 1 , , K 4 , C 4 , ( P 2 C 3 ) ) .
Figure 3. An example of ( 1 , 2 ) -kernel in P 6 ( P 4 , K 1 , , K 4 , C 4 , ( P 2 C 3 ) ) .
Symmetry 13 02399 g003
Figure 4. An example of the graph C 6 ( ( P 5 , K 1 , P 2 , N 3 , C 4 , K 4 ) ) .
Figure 4. An example of the graph C 6 ( ( P 5 , K 1 , P 2 , N 3 , C 4 , K 4 ) ) .
Symmetry 13 02399 g004
Figure 5. An example of ( 1 , 1 ) -kernel in P 6 ( ( P 3 , K 4 , N 2 , P 4 , P 3 , K 1 ) ) .
Figure 5. An example of ( 1 , 1 ) -kernel in P 6 ( ( P 3 , K 4 , N 2 , P 4 , P 3 , K 1 ) ) .
Symmetry 13 02399 g005
Figure 6. An example of ( 1 , 2 ) -kernel in P 6 ( ( P 3 , K 4 , N 2 , P 4 , P 3 , K 1 ) ) .
Figure 6. An example of ( 1 , 2 ) -kernel in P 6 ( ( P 3 , K 4 , N 2 , P 4 , P 3 , K 1 ) ) .
Symmetry 13 02399 g006
Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Share and Cite

MDPI and ACS Style

Michalski, A.; Bednarz, P. On Independent Secondary Dominating Sets in Generalized Graph Products. Symmetry 2021, 13, 2399. https://doi.org/10.3390/sym13122399

AMA Style

Michalski A, Bednarz P. On Independent Secondary Dominating Sets in Generalized Graph Products. Symmetry. 2021; 13(12):2399. https://doi.org/10.3390/sym13122399

Chicago/Turabian Style

Michalski, Adrian, and Paweł Bednarz. 2021. "On Independent Secondary Dominating Sets in Generalized Graph Products" Symmetry 13, no. 12: 2399. https://doi.org/10.3390/sym13122399

APA Style

Michalski, A., & Bednarz, P. (2021). On Independent Secondary Dominating Sets in Generalized Graph Products. Symmetry, 13(12), 2399. https://doi.org/10.3390/sym13122399

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Metrics

Back to TopTop