
Partial domination was proposed in 2017 on the basis of domination theory, which has good practical application background in communication network. Let G=(V,E) be a graph and F be a family of graphs, a subset S⊆V is called an F-isolating set of G if G[V∖NG[S]] does not contain F as a subgraph for all F∈F. The subset S is called an isolating set of G if F={K2} and G[V∖NG[S]] does not contain K2 as a subgraph. The isolation number of G is the minimum cardinality of an isolating set of G, denoted by ι(G). The hypercube network and n-star network are the basic models for network systems, and many more complex network structures can be built from them. In this study, we obtain the sharp bounds of the isolation numbers of the hypercube network and n-star network.
Citation: Shumin Zhang, Tianxia Jia, Minhui Li. Partial domination of network modelling[J]. AIMS Mathematics, 2023, 8(10): 24225-24232. doi: 10.3934/math.20231235
[1] | Ana Klobučar Barišić, Antoaneta Klobučar . Double total domination number in certain chemical graphs. AIMS Mathematics, 2022, 7(11): 19629-19640. doi: 10.3934/math.20221076 |
[2] | Bo Zhu, Shumin Zhang, Huifen Ge, Chengfu Ye . The $ g $-extra $ H $-structure connectivity and $ g $-extra $ H $-substructure connectivity of hypercubes. AIMS Mathematics, 2023, 8(10): 24848-24861. doi: 10.3934/math.20231267 |
[3] | Huifen Ge, Shumin Zhang, Chengfu Ye, Rongxia Hao . The generalized 4-connectivity of folded Petersen cube networks. AIMS Mathematics, 2022, 7(8): 14718-14737. doi: 10.3934/math.2022809 |
[4] | Abel Cabrera-Martínez, Andrea Conchado Peiró . On the $ \{2\} $-domination number of graphs. AIMS Mathematics, 2022, 7(6): 10731-10743. doi: 10.3934/math.2022599 |
[5] | Ahlam Almulhim . Signed double Italian domination. AIMS Mathematics, 2023, 8(12): 30895-30909. doi: 10.3934/math.20231580 |
[6] | Betül ATAY ATAKUL . Stability and domination exponentially in some graphs. AIMS Mathematics, 2020, 5(5): 5063-5075. doi: 10.3934/math.2020325 |
[7] | Shahid Zaman, Fouad A. Abolaban, Ali Ahmad, Muhammad Ahsan Asim . Maximum $ H $-index of bipartite network with some given parameters. AIMS Mathematics, 2021, 6(5): 5165-5175. doi: 10.3934/math.2021306 |
[8] | Abel Cabrera-Martínez, Andrea Conchado Peiró, Juan Manuel Rueda-Vázquez . Further results on the total Italian domination number of trees. AIMS Mathematics, 2023, 8(5): 10654-10664. doi: 10.3934/math.2023540 |
[9] | Zepeng Li . A note on the bounds of Roman domination numbers. AIMS Mathematics, 2021, 6(4): 3940-3946. doi: 10.3934/math.2021234 |
[10] | A. El-Mesady, Y. S. Hamed, M. S. Mohamed, H. Shabana . Partially balanced network designs and graph codes generation. AIMS Mathematics, 2022, 7(2): 2393-2412. doi: 10.3934/math.2022135 |
Partial domination was proposed in 2017 on the basis of domination theory, which has good practical application background in communication network. Let G=(V,E) be a graph and F be a family of graphs, a subset S⊆V is called an F-isolating set of G if G[V∖NG[S]] does not contain F as a subgraph for all F∈F. The subset S is called an isolating set of G if F={K2} and G[V∖NG[S]] does not contain K2 as a subgraph. The isolation number of G is the minimum cardinality of an isolating set of G, denoted by ι(G). The hypercube network and n-star network are the basic models for network systems, and many more complex network structures can be built from them. In this study, we obtain the sharp bounds of the isolation numbers of the hypercube network and n-star network.
In this paper, all graphs considered are non-empty, finite, undirected and simple. Additionally, for standard graph theory terminology not given here, we refer to [1]. Let G be a simple graph with the vertex set V(G) and the edge set E(G), and |V(G)|=n, |E(G)|=m. For any v∈V(G), the degree dG(v) of v is the number of neighbors of v. The minimum and maximum degree of G are denoted by δ(G) and Δ(G), respectively. The open neighborhood NG(v) of v is the set N(v)={u∈V|uv∈E} and the closed neighborhood of v is the set NG[v]=NG(v)∪{v}. For any S⊆V(G), the open neighborhood of S is the set NG(S)=⋃v∈SNG(v) and the closed neighborhood of S is the set NG[S]=NG(S)∪S. Furthermore, we define NS(v)=NG(v)∩S and NS[v]=NS(v)∪{v}. The subgraph of G induced by S is denoted by G[S]. For a graph H, we say that G is H-free if G does not contain H as a subgraph. The cycle and clique on n vertices are denoted as Cn and Kn. Abbreviate {1,2,⋯,n} to [n] and say "i" is a symbol of [n], where n∈N∗ and i∈[n].
In recent years, with the rapid development of information technology, the domination theory has been widely used in computer technology, cryptography, social network, communication network and many other subjects. In 1958, Claude Berge [2] first proposed the concept of the domination number. A vertex subset S⊆V(G) is a dominating set of G if NG[S]=V(G). The domination number γ(G) of G is the minimum cardinality of a dominating set of G, i.e γ(G)=min{|S|:SisadominatingsetofG}.
In 2017, Caro and Hansberg [3] extended the domination to the partial domination, and proposed the concept of an F-isolating set of a graph G for the first time. Let G=(V,E) be a graph and F be a family of graphs.
Definition 1.1. [3] A subset S⊆V is called an F-isolating set of G if G[V∖NG[S]] does not contain F as a subgraph for all F∈F. The F-isolation number of G is the minimum cardinality of an F-isolating set of G, denoted by ι(G,F).
In particalur, if F={Kk}, the set S is called a {Kk}-isolating set of G if G[V∖NG[S]] does not contain Kk as a subgraph, and the {Kk}-isolation number of G is the minimum cardinality of a {Kk}-isolating set of G, denoted by ι(G,k). For any positive integer k, if F={K1,k+1}, the set S is called a k-isolating set of G if G[V∖NG[S]] does not contain K1,k+1 as a subgraph, and the k-isolation number of G is the minimum cardinality of a k-isolating set of G, denoted by ιk(G). Especially, when k=0, the set S is called an isolating set of G, and the minimum cardinality of an isolating set of G is the isolation number of G, denoted by ι(G).
With respect to this problem, Borg et al. [4] studied the ι(G,k) of a connected graph G is at most nk+1 unless G≅Kk, or k=2 and G≅C5. Caro and Hansberg [3] investigated that ι(G)≤n3 for n≥6, ιk(T)≤nk+3 of a tree T which is different from K1,k+1, ιk(G)≤n4 of a maximal outerplanar graph G with n≥4 and so on. Tokunaga et al. [5] studied that if G is a maximal outerplanar graph of order n with n2 vertices of degree 2, then ι(G)≤n+n25 when n2≤n4, and ι(G)≤n−n23 otherwise. Borg and Kaemawichanurat [6] showed that if G is a maximal outerplanar graph with n≥5, then ι1(G)≤n5, they also showed that ι1(G)≤n+n26 when n2≤n3, and ι1(G)≤n−n23 otherwise, where n2 is the number of vertices of degree 2. Borg and Kaemawichanurat [7] obtained that ιk(G)≤min{nk+4,n+n25,n−n23} for a maximal outerplanar graph G and k≥0, where n2 is the number of vertices of degree 2. Vazquez-Araujo [8] analyzed that ι(T)=n3 implies ι(T)=γ(T) for a tree T, and proposed simple algorithms to build these trees from the connections of stars.
For a {Kk}-isolating set S, in 2021, Favaron and Kaemawichanurat [9] restriced the induced subgraph G[S] to be an independent set and introduced the concept of the independent {Kk}-isolation number of G. The vertex subset S⊆V is said to be independent {Kk}-isolating if S is a {Kk}-isolating set of G and G[S] has no edge. The independent {Kk}-isolation number of G is the minimum cardinality of an independent {Kk}-isolating set of G. Based on the concept, we propose the following concepts.
Definition 1.2. A subset S⊆V is called an independent F-isolating set of G if S is an F-isolating set of G and S is an independent set. The independent F-isolation number of G is the minimum cardinality of an independent F-isolating set of G, denoted by ιI(G,F).
Definition 1.3. A subset S⊆V is called an independent isolating set of G if S is an isolating set of G and G[S] has no edge. The independent isolation number of G is the minimum cardinality of an independent isolating set of G, denoted by ιI(G).
In this paper, we investigate respectively the sharp bounds of the isolation number and the independent isolation number of the hypercube network and n-star network.
The hypercube network is the basic model for interconnection networks, and it is a popular network because of its attractive properties, including regularity, symmetry, small diameter, strong connectivity, recursive construction, partitionability and relatively low link complexity [10,11]. In general, a network model can be modeled as a graph. Let n be a positive integer. The hypercube network of dimension n, denoted by Qn, is the simple graph whose vertices are the n-tuples with entries in {0,1} and whose edges are the pairs of n-tuples that differ in exactly one position (see Figure 1). A m-dimensional subcube of Qn is isomorphic to Qm for any positive integer 1≤m≤n. A vertex of V(Qn) is an even vertex if the number of 1s is even in its all symbols. A vertex of V(Qn) is an odd vertex if the number of 1s is odd in its all symbols.
The hypercube network have many classic and fascinating topological structural properties, such as those below.
Lemma 2.1. [1] Hypercube network satisfies the following properties:
(a) |V(Qn)|=2n, |E(Qn)|=n⋅2n−1;
(b) Each edge of Qn has an even endvertex and an odd endvertex;
(c) Qn is a n-regular bipartite graph;
(d) Every perfect matching of Qn has 2n−1 edges;
(e) If n≥3, then Qn has 2n−3 disjoint 3-dimensional subcubes of Qn.
By Lemma 2.1, we obtain the following results.
Theorem 2.2. ι(Q2)=1, ι(Q3)=ι(Q4)=2.
Proof. According to the structure of Qn, we know that Q2≅C4, so ι(Q2)=ι(C4)=1.
It is easy to know {(0,0,0),(1,1,1)} is an isolating set of Q3 (see Figure 1(b)), so ι(Q3)≤2. Let S1 be a minimum isolating set of Q3, clearly, |S1|≥1. Suppose that |S1|=1. If the vertex of S1 is an even vertex, without loss of generality, let S1={(1,1,0)}, then V(Q3)∖NQ3[S1]={(0,0,0),(0,0,1),(1,0,1),(0,1,1)}. Hence, V(Q3)∖NQ3[S1] is not an independent set of Q3, which is a contradiction. If the vertex of S1 is an odd vertex, without loss of generality, let S1={(0,1,0)}, then V(Q3)∖NQ3[S1]={(1,0,0),(0,0,1),(1,0,1),(1,1,1)}. Hence, V(Q3)∖NQ3[S1] is not an independent set of Q3, which is a contradiction. Thus, |S1|≠1, furthermore, ι(Q3)=|S1|≥2. Hence, ι(Q3)=2.
Additionally, it is easy to know {(0,0,0,0),(1,1,1,1)} is an isolating set of Q4 (see Figure 1(c)), so ι(Q4)≤2. Let Q13 and Q23 be two disjoint 3-dimensional subcubes of Q4 by Lemma 2.1(e), and S2 be a minimum isolating set of Q4. Obviously, |S2|≥1. If |S2|=1 and S2={v}, then v∈Qi3 for any i∈{1,2}. Since Qj3⊂G[V(Q4)∖NQ4[v]] for j∈{1,2}∖{i}, V(Q4)∖NQ4[S2] is not an independent set of Q4, which is a contradiction. Thus, |S2|≠1, furthermore, ι(Q4)=|S2|≥2. Hence, ι(Q4)=2.
Theorem 2.3. Let n be a positive integer and n≥4, then 2n−1n≤ι(Qn)≤2n−3. Moreover, the bounds are sharp.
Proof. Let S be a minimum {K2}-isolating set of Qn. Since every perfect matching of Qn has 2n−1 edges and V(Qn)∖NQn[S] is an independent set, every edge of a perfect matching of Qn has at least one vertex in NQn(S), that is, |NQn(S)|≥2n2=2n−1. By Lemma 2.1(c), we have |NQn(S)|≤Δ(Qn)|S|=d(v)|S|=n|S| for any vertex v∈S. Thus, ι(Qn)=|S|≥|NQn(S)|d(v)≥2n−1d(v)=2n−1n.
By Lemma 2.1, we know that Qn has 2n−3 disjoint 3-dimensional subcubes of Qn for n≥4 and each edge of Qn has one even endvertex and one odd endvertex, so each Q3 has four odd vertices and four even vertices, and every even vertex is adjacent to three odd vertices in Q3. Without loss of generality, let x∈V(Q13) be an even vertex and y∈V(Q13)∖NQ13[x] be an odd vertex of Q13. Since n≥4, there exists a Qi3(2≤i≤2n−3) such that |NQn(x)∩V(Qi3)|=1. Let NQn(x)∩V(Qi3)={x′} and y′∈V(Qi3)∖NQi3[x′] be an even vertex of Qi3. By the structure of Qn, we know that N(x)∩V(Qi3)={x′}, N(y)∩V(Qi3)={y′} and yy′ is an edge, then all vertices of (V(Q13)∪V(Qi3))∖NQn[{x,y′}] are even vertices, and {x,y′} is an isolating set of Q13∪Qi3. Choose one even vertex in each Qj3(1≤j≤2n−3) as the set S such that all vertices of V(Qn)∖NQn[S] are even vertices (In Figure 2, a,b,c,d are even vertices of V(Q5) and {a,b,c,d} is an isolating set of Q5). Since each edge of Qn has an even endvertex and an odd endvertex, the set V(Qn)∖NQn[S] is an independent set of Qn, thus the set S is an isolating set of Qn. Since |S∩V(Qj3)|=1 for 1≤j≤2n−3, we obtain ι(Qn)≤|S|=2n−3. In conclusion, 2n−1n≤ι(Qn)≤2n−3 for n≥4.
Especially, if 2n−1n=2n−3, then n=4. So the upper bound is equal to the lower bound if and only if n=4. If n=4, then ι(Qn)=2=2n−3=2n−1n by Theorem 2.2. Thus, the upper and lower bounds are sharp.
Corollary 2.4. Let n be a positive integer and n≥4, then 2n−1n≤ιI(Qn)≤2n−3. Moreover, the bounds are sharp.
Proof. Let SI be a minimum independent isolaing set of Qn. Obviously, SI is an isolating set of Qn. Thus, by Theorem 2.2, we have ιI(Qn)≥2n−1n. Let {Q13,Q23,⋯,Q2n−33} be the set of 2n−3 disjoint 3-dimensional subcubes of Qn. Choose one even vertex in each Qi3(1≤i≤2n−3) as the set S such that all vertices of V(Qn)∖NQn[S] are even vertices. According to the proof of Theorem 2.2, the set S is an isolating set of Qn and ι(Qn)≤2n−3. Since all vertices of S are even vertices, the set S is an independent isolating set of Qn. Thus ιI(Qn)≤2n−3. In conclusion, 2n−1n≤ιI(Qn)≤2n−3 for n≥4.
Especially, if n=4, then ι(Qn)=2=2n−3=2n−1n by Theorem 2.2. Thus, the upper and lower bounds are sharp.
The n-star network was proposed by Akers, Harel and Krishnamurthy [12] as an attractive alternative to the hypercube network for interconnecting processors on a parallel computer. For a positive integer n(n≥2), the n-star network on n symbols, denoted by Sn, is the graph with n! vertices, whose the vertex set V(Sn) is all permutations of symbols 1,2,⋯,n, and each vertex v∈V(Sn) is connected to n−1 vertices which can be obtained by interchanging the first symbol of v with the ith symbol of v for 2≤i≤n (S4 is shown as an example in Figure 3).
Lemma 2.5. [13,14] Let G be an n-vertex graph with minimum degree δ(G). If δ(G)≥1, then γ(G)≤n2.
Theorem 2.6. Let n be a positive integer and n≥2, then n⋅(n−2)!2≤ι(Sn)≤(n−1)!. Moreover, the bounds are sharp.
Proof. Let S be a minimum isolating set of Sn. According to the structure of Sn, we know that Sn is a (n−1)-regular bipartite graph, and every perfect matching of Sn has n!2 edges. Note that S is a minimum isolating set of Sn and V(Sn)∖NSn[S] is an independent set, then every edge of a perfect matching of Sn has at least one endvertex in NSn(S), that is, |NSn(S)|≥n!2. For any vertex v∈S, we have |NSn(S)|≤Δ(Sn)|S|=d(v)|S|=(n−1)|S|. Thus, ι(Sn)=|S|≥|NSn(S)|d(v)≥n!2n−1=n⋅(n−2)!2.
Inspired by Alon and Spencer [15] and Caroa and Hansbergb [3], we show that ι(Sn)≤(n−1)! by the probabilistic method. Since n≥2, d(v)=n−1≥1 for any vertex v∈V(Sn). Let p∈[0,1], and we independently select a vertex subset A⊂V(Sn) at random such that P(v∈A)=p. Let I be the set of the isolated vertices of V(Sn)∖A. Meanwhile, let B=V(Sn)∖(NSn[A]∪I) and D be a minimum dominating set of G[B]. Since there is no isolated vertice in B, δ(G[B])≥1, furthermore, γ(G[B])=|D|≤|B|2 by Lemma 2.5. Thus, A∪D is an isolating set of Sn. Note that the expectated value E[|D|]≤E[|B|2]=12E[|B|]. Hence, we have
P(v∈B)=P(v∈B)=P(v∈V(Sn)∖(NSn[A]∪I))=P(v∈V(Sn)∖NSn[A]) |
=(1−p)d(v)+1=(1−p)n−1+1=(1−p)n. |
Thus, we obtain that
E[|A∪D|]≤E[|A|]+12E[|B|]=p|V(Sn)|+12(1−p)n|V(Sn)|=(p+12(1−p)n)⋅(n!). |
Considering the function f(p)=(p+12(1−p)n)⋅(n!) and its derivative f′(p)=(1−12n(1−p)n−1⋅(n!), we can see that f′(p)=0 when p=1−(2n)1n−1. It follows that
ι(Sn)≤E[|A∪D|]≤(p+12(1−p)n)⋅(n!)≤(1−(2n)1n−1+12((2n)1n−1)n)⋅(n!) |
=(1−(2n)1n−1+12(2n)(2n)1n−1)⋅(n!). |
Since n≥2, we have (2n)1n−1≤1. Then ι(Sn)≤(1−1+12(2n)⋅(n!)=1n⋅(n!)=(n−1)!.
In conclusion, n⋅(n−2)!2≤ι(Sn)≤(n−1)! for any positive integer n≥2.
Especially, if n=2, then S2≅K2, and ι(K2)=1=2⋅0!2=n⋅(n−2)!2. If n=3, then S3≅C6, and ι(C6)=2=(3−1)!=(n−1)!. Hence, the bounds are sharp.
Corollary 2.7. Let n be a positive integer and n≥2, then n⋅(n−2)!2≤ιI(Sn)≤(n−1)!. Moreover, the bounds are sharp.
Proof. Let SI be a minimum independent isolaing set of Sn. Obviously, SI is also an isolating set of Sn. By Theorem 2.6, we have ιI(Sn)≥n⋅(n−2)!2. Let V1 be the set of all vertices with the first symbol is 1. Clearly, the set V1 is an independent set of Sn. According the structure of Sn, we know that any vertex of V1 has different n−1 neighbors, and the first symbol of these n−1 neighbors is 2,3,⋯,n−1,n respectively. Let x, y∈V1 and x≠y. If NSn(x)∩NSn(y)≠∅, then there exists a vertex to be adjacent to x and y, which contradicts the definition of Sn. Thus, NSn(x)∩NSn(y)=∅, that is, the neighborhoods of any two vertices of V1 are disjoint. Hence, |NSn[V1]|=(n−1)⋅|V1|+|V1|=n⋅|V1|=n⋅(n−1)!=n!=|V(Sn)|, this means that G[V(Sn)∖NSn[V1]] has no edge. Since V1 is independent, the set V1 is an independent isolating set of Sn. Then ιI(Sn)≤|V1|=(n−1)!. In conclusion, n⋅(n−2)!2≤ιI(Sn)≤(n−1)! for any positive integer n≥2.
Especially, if n=2, then {(1,2)} is an independent isolating set of S2. Thus, ιI(S2)=1=2⋅0!2=n⋅(n−2)!2. If n=3, then {(1,2,3),(1,3,2)} is an independent isolating set of S3. Thus, ιI(S3)=2=(3−1)!=(n−1)!. Hence, the bounds are sharp.
The hypercube network Qn and n-star network Sn are both recursively constructed networks, and they have many known and attractive topological properties. This paper demonstrates the sharp bounds of the isolation number and the independent isolation number of the hypercube network and n-star network. In view of this research direction, there are still many academic issues worth studying:
Problem 1. Let m≥1 be a positive integar and F={F1,F2,⋯,Fm}. For any Fi∈F, if Fi≆K2, what Fi can be used to explore the F-isolation number of the hypercube network or n-star network?
Problem 2. Consider the F-isolation number of some other network models.
For future work, it would be interesting and meaningful to probe and research the F-isolation number of some other network models.
The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.
This work is supported by the Science Found of Qinghai Province (No. 2021-ZJ-703), and the National Science Foundation of China (Nos.11661068, 12261074 and 12201335).
The authors are grateful to the reviewers for their helpful suggestions and comments.
All authors declare no conflicts of interest in this paper.
[1] | D. B. West, Introduction to graph theory, 2 Eds., Upper Saddle River, NJ: Prentice Hall, 2001. |
[2] | C. Berge, The theory of graphs and its applications, Paris: Dunod, 1958. |
[3] |
Y. Caroa, A. Hansbergb, Partial domination-the isolation number of a graph, Filomath, 31 (2017), 3925–3944. https://doi.org/10.2298/FIL1712925C doi: 10.2298/FIL1712925C
![]() |
[4] |
P. Borg, K. Fenech, P. Kaemawichanurat, Isolation of k-cliques, Discrete Math., 343 (2020), 1–7. https://doi.org/10.1016/j.disc.2020.111879 doi: 10.1016/j.disc.2020.111879
![]() |
[5] |
S. Tokunaga, T. Jiarasuksakun, P. Kaemawichanurat, Isolation number of maximal outerplanar graphs, Discrete Appl. Math., 267 (2019), 215–218. https://doi.org/10.1016/j.dam.2019.06.011 doi: 10.1016/j.dam.2019.06.011
![]() |
[6] |
P. Borg, P. Kaemawichanurat, Partial domination of maximal outerplanar graphs, Discrete Appl. Math., 283 (2020), 306–314. https://doi.org/10.1016/j.dam.2020.01.005 doi: 10.1016/j.dam.2020.01.005
![]() |
[7] | P. Borg, P. Kaemawichanurat, A generalization of the Art Gallery Theorem, arXiv Press, 2020. https://doi.org/10.48550/arXiv.2002.06014 |
[8] |
M. Lemańska, M. J. Souto-Salorio, A. Dapena, F. J. Vazquez-Araujo, Isolation number versus domination number of trees, Mathematics, 9 (2021), 1–10. https://doi.org/10.3390/math9121325 doi: 10.3390/math9121325
![]() |
[9] |
O. Favaron, P. Kaemawichanurat, Inequalities between the Kk-isolation number and the independent Kk-isolation number of a graph, Discrete Appl. Math., 289 (2021), 93–97. https://doi.org/10.1016/j.dam.2020.09.011 doi: 10.1016/j.dam.2020.09.011
![]() |
[10] |
Y. Saad, M. H. Schultz, Topological properties of hypercubes, IEEE Trans. Comput., 37 (1988), 867–872. https://doi.org/10.1109/12.2234 doi: 10.1109/12.2234
![]() |
[11] |
A. K. Somani, O. Peleg, On diagnosability of large fault sets in regular topology-based computer systems, IEEE Trans. Comput., 45 (1996), 892–903. https://doi.org/10.1109/12.536232 doi: 10.1109/12.536232
![]() |
[12] | S. B. Akers, D. Horel, B. Krishnamurthy, The star graph: an attractive alternative to the n-cube, Proceedings of International Conference on Parallel Processing, 1987,393–400. |
[13] | T. W. Haynes, S. T. Hedetniemi, P. J. Slater, Fundamentals of domination in graphs, New York, NY: Marcel Dekker, 1998. |
[14] | O. Ore, Theory of graphs, Americal Mathematial Society, Providence, 1962. |
[15] | N. Alon, J. H. Spencer, The probabilistic method, 3 Eds., Hoboken, NJ, USA: Wiley, 2008. |