Research article Special Issues

Partial domination of network modelling

  • 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 SV is called an F-isolating set of G if G[VNG[S]] does not contain F as a subgraph for all FF. The subset S is called an isolating set of G if F={K2} and G[VNG[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

    Related Papers:

    [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 SV is called an F-isolating set of G if G[VNG[S]] does not contain F as a subgraph for all FF. The subset S is called an isolating set of G if F={K2} and G[VNG[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 vV(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)={uV|uvE} and the closed neighborhood of v is the set NG[v]=NG(v){v}. For any SV(G), the open neighborhood of S is the set NG(S)=vSNG(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 nN 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 SV(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 SV is called an F-isolating set of G if G[VNG[S]] does not contain F as a subgraph for all FF. 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[VNG[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[VNG[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 GKk, or k=2 and GC5. Caro and Hansberg [3] investigated that ι(G)n3 for n6, ι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 n4 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 n2n4, and ι(G)nn23 otherwise. Borg and Kaemawichanurat [6] showed that if G is a maximal outerplanar graph with n5, then ι1(G)n5, they also showed that ι1(G)n+n26 when n2n3, and ι1(G)nn23 otherwise, where n2 is the number of vertices of degree 2. Borg and Kaemawichanurat [7] obtained that ιk(G)min{nk+4,n+n25,nn23} for a maximal outerplanar graph G and k0, 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 SV 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 SV 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 SV 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 1mn. 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.

    Figure 1.  (a)Q2; (b)Q3; (c)Q4.

    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)|=n2n1;

    (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 2n1 edges;

    (e) If n3, then Qn has 2n3 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 Q2C4, 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 vQi3 for any i{1,2}. Since Qj3G[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 n4, then 2n1nι(Qn)2n3. Moreover, the bounds are sharp.

    Proof. Let S be a minimum {K2}-isolating set of Qn. Since every perfect matching of Qn has 2n1 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=2n1. By Lemma 2.1(c), we have |NQn(S)|Δ(Qn)|S|=d(v)|S|=n|S| for any vertex vS. Thus, ι(Qn)=|S||NQn(S)|d(v)2n1d(v)=2n1n.

    By Lemma 2.1, we know that Qn has 2n3 disjoint 3-dimensional subcubes of Qn for n4 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 xV(Q13) be an even vertex and yV(Q13)NQ13[x] be an odd vertex of Q13. Since n4, there exists a Qi3(2i2n3) such that |NQn(x)V(Qi3)|=1. Let NQn(x)V(Qi3)={x} and yV(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 Q13Qi3. Choose one even vertex in each Qj3(1j2n3) 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 |SV(Qj3)|=1 for 1j2n3, we obtain ι(Qn)|S|=2n3. In conclusion, 2n1nι(Qn)2n3 for n4.

    Figure 2.  a={0,0,0,0,0}, b={0,1,1,1,1}, c={1,0,1,1,1}, d={1,1,0,0,0}.

    Especially, if 2n1n=2n3, 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=2n3=2n1n by Theorem 2.2. Thus, the upper and lower bounds are sharp.

    Corollary 2.4. Let n be a positive integer and n4, then 2n1nιI(Qn)2n3. 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)2n1n. Let {Q13,Q23,,Q2n33} be the set of 2n3 disjoint 3-dimensional subcubes of Qn. Choose one even vertex in each Qi3(1i2n3) 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)2n3. Since all vertices of S are even vertices, the set S is an independent isolating set of Qn. Thus ιI(Qn)2n3. In conclusion, 2n1nιI(Qn)2n3 for n4.

    Especially, if n=4, then ι(Qn)=2=2n3=2n1n 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(n2), 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 vV(Sn) is connected to n1 vertices which can be obtained by interchanging the first symbol of v with the ith symbol of v for 2in (S4 is shown as an example in Figure 3).

    Figure 3.  S4.

    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 n2, then n(n2)!2ι(Sn)(n1)!. 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 (n1)-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 vS, we have |NSn(S)|Δ(Sn)|S|=d(v)|S|=(n1)|S|. Thus, ι(Sn)=|S||NSn(S)|d(v)n!2n1=n(n2)!2.

    Inspired by Alon and Spencer [15] and Caroa and Hansbergb [3], we show that ι(Sn)(n1)! by the probabilistic method. Since n2, d(v)=n11 for any vertex vV(Sn). Let p[0,1], and we independently select a vertex subset AV(Sn) at random such that P(vA)=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, AD is an isolating set of Sn. Note that the expectated value E[|D|]E[|B|2]=12E[|B|]. Hence, we have

    P(vB)=P(vB)=P(vV(Sn)(NSn[A]I))=P(vV(Sn)NSn[A])
    =(1p)d(v)+1=(1p)n1+1=(1p)n.

    Thus, we obtain that

    E[|AD|]E[|A|]+12E[|B|]=p|V(Sn)|+12(1p)n|V(Sn)|=(p+12(1p)n)(n!).

    Considering the function f(p)=(p+12(1p)n)(n!) and its derivative f(p)=(112n(1p)n1(n!), we can see that f(p)=0 when p=1(2n)1n1. It follows that

    ι(Sn)E[|AD|](p+12(1p)n)(n!)(1(2n)1n1+12((2n)1n1)n)(n!)
    =(1(2n)1n1+12(2n)(2n)1n1)(n!).

    Since n2, we have (2n)1n11. Then ι(Sn)(11+12(2n)(n!)=1n(n!)=(n1)!.

    In conclusion, n(n2)!2ι(Sn)(n1)! for any positive integer n2.

    Especially, if n=2, then S2K2, and ι(K2)=1=20!2=n(n2)!2. If n=3, then S3C6, and ι(C6)=2=(31)!=(n1)!. Hence, the bounds are sharp.

    Corollary 2.7. Let n be a positive integer and n2, then n(n2)!2ιI(Sn)(n1)!. 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(n2)!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 n1 neighbors, and the first symbol of these n1 neighbors is 2,3,,n1,n respectively. Let x, yV1 and xy. 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]|=(n1)|V1|+|V1|=n|V1|=n(n1)!=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|=(n1)!. In conclusion, n(n2)!2ιI(Sn)(n1)! for any positive integer n2.

    Especially, if n=2, then {(1,2)} is an independent isolating set of S2. Thus, ιI(S2)=1=20!2=n(n2)!2. If n=3, then {(1,2,3),(1,3,2)} is an independent isolating set of S3. Thus, ιI(S3)=2=(31)!=(n1)!. 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 m1 be a positive integar and F={F1,F2,,Fm}. For any FiF, if FiK2, 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.
  • Reader Comments
  • © 2023 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(1328) PDF downloads(66) Cited by(0)

Figures and Tables

Figures(3)

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog