The Experts below are selected from a list of 360 Experts worldwide ranked by ideXlab platform
Jia Guo - One of the best experts on this subject based on the ideXlab platform.
-
edge fault tolerant strong menger edge connectivity of Bubble Sort star graphs
Discrete Applied Mathematics, 2021Co-Authors: Jia GuoAbstract:Abstract The connectivity and edge connectivity of interconnection network determine the fault tolerance of the network. An interconnection network is usually viewed as a connected graph, where vertex corresponds processor and edge corresponds link between two distinct processors. Given a connected graph G with vertex set V ( G ) and edge set E ( G ) , if for any two distinct vertices u , v ∈ V ( G ) , there exist min { d G ( u ) , d G ( v ) } edge-disjoint paths between u and v , then G is strongly Menger edge connected. Let m be an integer with m ≥ 1 . If G − F e remains strongly Menger edge connected for any F e ⊆ E ( G ) with | F e | ≤ m , then G is m -edge-fault-tolerant strongly Menger edge connected. If G − F e is strongly Menger edge connected for any F e ⊆ E ( G ) with | F e | ≤ m and δ ( G − F e ) ≥ 2 , then G is m -conditional edge-fault-tolerant strongly Menger edge connected. In this paper, we consider the n -dimensional Bubble-Sort star graph B S n . We show that B S n is ( 2 n − 5 ) -edge-fault-tolerant strongly Menger edge connected for n ≥ 3 and ( 6 n − 17 ) -conditional edge-fault-tolerant strongly Menger edge connected for n ≥ 4 . Moreover, we give some examples to show that our results are optimal.
-
vertex pancyclicity of the n k Bubble Sort networks
Theoretical Computer Science, 2021Co-Authors: Xin Wang, Jia GuoAbstract:Abstract The cycle embedding is an important problem of networks, which can determine the fault tolerance of the networks. A network can be viewed as a graph. Let m be an integer with m ≥ 4 , G be a graph and w ∈ V ( G ) be an arbitrary vertex. The graph G is vertex-pancyclic if G has a cycle C l of length l with w ∈ V ( C l ) for every l ∈ { 3 , 4 , ⋯ , | V ( G ) | } and G is m-weak-vertex-pancyclic if G has a cycle C l of length l with w ∈ V ( C l ) for every l ∈ { m , m + 1 , ⋯ , | V ( G ) | } . Let G ′ be a bipartite graph and w ′ ∈ V ( G ′ ) be an arbitrary vertex. The graph G ′ is vertex-bipancyclic if G ′ has a cycle C h of length h with w ′ ∈ V ( C h ) for any even integer h with 4 ≤ h ≤ | V ( G ′ ) | . In this paper, we study the cycle embedding in the ( n , k ) -Bubble-Sort network B n , k . We obtain that (1) B n , 1 is vertex-pancyclic for n ≥ 3 . (2) B n , n − 1 is vertex-bipancyclic for n ≥ 4 . (3) B 4 , 2 and B 5 , 2 are 6-weak-vertex-pancyclic and B 5 , 3 is vertex-pancyclic. (4) B n , k is vertex-pancyclic for n ≥ 6 with 2 ≤ k ≤ n − 2 and every constructed cycle of B n , k contains a residual edge for n ≥ 4 with 2 ≤ k ≤ n − 2 .
-
the strong matching preclusion of Bubble Sort star graphs
arXiv: Combinatorics, 2020Co-Authors: Jia Guo, Wei HuoAbstract:The (strong) matching preclusion number is a measure of the performance of the interconnection network in the event of (vertex and) edge failure, which is defined as the minimum number of (vertices and) edges whose deletion results in the remaining network that has neither a perfect matching nor an almost-perfect matching. The Bubble-Sort star graph is one of the validly discussed interconnection networks. In this paper, we show that the strong matching preclusion number of an $n$-dimensional Bubble-Sort star graph $BS_n$ is $2$ for $n\geq3$ and each optimal strong matching preclusion set of $BS_n$ is a set of two vertices from the same bipartition set. Moreover, we get that the matching preclusion number of $BS_n$ is $2n-3$ for $n\geq3$ and that every optimal matching preclusion set of $BS_n$ is trivial.
-
matching preclusion and strong matching preclusion of the Bubble Sort star graphs
arXiv: Combinatorics, 2020Co-Authors: Xin Wang, Jia GuoAbstract:Since a plurality of processors in a distributed computer system working in parallel, to ensure the fault tolerance and stability of the network is an important issue in distributed systems. As the topology of the distributed network can be modeled as a graph, the (strong) matching preclusion in graph theory can be used as a robustness measure for missing edges in parallel and distributed networks, which is defined as the minimum number of (vertices and) edges whose deletion results in the remaining network that has neither a perfect matching nor an almost-perfect matching. The Bubble-Sort star graph is one of the validly discussed interconnection networks related to the distributed systems. In this paper, we show that the strong matching preclusion number of an $n$-dimensional Bubble-Sort star graph $BS_n$ is $2$ for $n\geq3$ and each optimal strong matching preclusion set of $BS_n$ is a set of two vertices from the same bipartition set. Moreover, we show that the matching preclusion number of $BS_n$ is $2n-3$ for $n\geq3$ and that every optimal matching preclusion set of $BS_n$ is trivial.
-
edge bipancyclicity of Bubble Sort star graphs
IEEE Access, 2019Co-Authors: Jia GuoAbstract:The topology of interconnection networks determines the performance of the networks. Linear arrays and rings are two of the most fundamental structures of the interconnection network topologies owing to their simple structures and low degree. Thus how to embed cycles and paths into interconnection networks is a crucial factor for the networks. The interconnection network considered in this paper is the Bubble-Sort star graph. The n-dimensional Bubble-Sort star graph BS n is a bipartite and (2n - 3)-regular graph of order n!. A bipartite graph G of order IV(G)I is edge-bipancyclic if each edge of G lies on a cycle of all even length l with 4 ≤ l ≤ |V(G)|. In this paper, we show that the n-dimensional Bubble-Sort star graph BSn is edge-bipancyclic for n ≥ 3 and for each even length l with 4 ≤ l ≤ n!, every edge of BSn lies on at least four different cycles of length l. Moreover, we also have that BSn is vertex-bipancyclic and bipancyclic for n ≥ 3.
Toru Araki - One of the best experts on this subject based on the ideXlab platform.
-
hamiltonian laceability of Bubble Sort graphs with edge faults
Information Sciences, 2007Co-Authors: Toru Araki, Yosuke KikuchiAbstract:It is known that the n-dimensional Bubble-Sort graph B"n is bipartite, (n-1)-regular, and has n! vertices. We first show that, for any vertex v, B"n-v has a hamiltonian path between any two vertices in the same partite set without v. Let F be a subset of edges of B"n. We next show that B"n-F has a hamiltonian path between any two vertices of different partite sets if |F| is at most n-3. Then we also prove that B"n-F has a path of length n!-2 between any pair of vertices in the same partite set.
-
edge bipancyclicity and edge fault tolerant bipancyclicity of Bubble Sort graphs
Information Processing Letters, 2006Co-Authors: Yosuke Kikuchi, Toru ArakiAbstract:A bipartite graph G is bipancyclic if G has a cycle of length l for every even 4 ≤ l ≤ |V(G)|. For a bipancyclic graph G and any edge e, G is edge-bipancyclic if e lies on a cycle of any even length l of G. In this paper, we show that the Bubble-Sort graph Bn is bipancyclic for n ≥ 4 and also show that it is edge-bipancyclic for n ≥ 5. Assume that F is a subset of E(Bn). We prove that Bn - F is bipancyclic, when n ≥ 4 and |F| ≤ n-3. Since Bn is a (n - 1)-regular graph, this result is optimal in the worst case.
-
edge bipancyclicity and edge fault tolerant bipancyclicity of Bubble Sort graphs
International Symposium on Parallel Architectures Algorithms and Networks, 2005Co-Authors: Yosuke Kikuchi, Toru ArakiAbstract:A bipartite graph G is bipancyclic if G has a cycle of length l for every even 4 /spl les/l/spl les/|V(G)|. For a bipancyclic graph G and any edge e, G is edge-bipancyclic if e lies on a cycle of any even length I of G. In this paper, we show that the Bubble-Sort graph B/sub n/ is bipancyclic for n/spl ges/ 4, and also show that it is edge-bipancyclic for n/spl ges/5. To obtain this results, we also prove that we can construct a hamiltonian cycle of B/sub n/ that contains given two nonadjacent edges. Assume that F is the subset of E(B/sub n/). We prove that B/sub n /-F is bipancyclic whenever n /spl ges/4 and |F|/spl les/ n-3. Since B/sub n/ is a (n-1)-regular graph, this result is optimal in the worst case.
Yosuke Kikuchi - One of the best experts on this subject based on the ideXlab platform.
-
hamiltonian laceability of Bubble Sort graphs with edge faults
Information Sciences, 2007Co-Authors: Toru Araki, Yosuke KikuchiAbstract:It is known that the n-dimensional Bubble-Sort graph B"n is bipartite, (n-1)-regular, and has n! vertices. We first show that, for any vertex v, B"n-v has a hamiltonian path between any two vertices in the same partite set without v. Let F be a subset of edges of B"n. We next show that B"n-F has a hamiltonian path between any two vertices of different partite sets if |F| is at most n-3. Then we also prove that B"n-F has a path of length n!-2 between any pair of vertices in the same partite set.
-
edge bipancyclicity and edge fault tolerant bipancyclicity of Bubble Sort graphs
Information Processing Letters, 2006Co-Authors: Yosuke Kikuchi, Toru ArakiAbstract:A bipartite graph G is bipancyclic if G has a cycle of length l for every even 4 ≤ l ≤ |V(G)|. For a bipancyclic graph G and any edge e, G is edge-bipancyclic if e lies on a cycle of any even length l of G. In this paper, we show that the Bubble-Sort graph Bn is bipancyclic for n ≥ 4 and also show that it is edge-bipancyclic for n ≥ 5. Assume that F is a subset of E(Bn). We prove that Bn - F is bipancyclic, when n ≥ 4 and |F| ≤ n-3. Since Bn is a (n - 1)-regular graph, this result is optimal in the worst case.
-
edge bipancyclicity and edge fault tolerant bipancyclicity of Bubble Sort graphs
International Symposium on Parallel Architectures Algorithms and Networks, 2005Co-Authors: Yosuke Kikuchi, Toru ArakiAbstract:A bipartite graph G is bipancyclic if G has a cycle of length l for every even 4 /spl les/l/spl les/|V(G)|. For a bipancyclic graph G and any edge e, G is edge-bipancyclic if e lies on a cycle of any even length I of G. In this paper, we show that the Bubble-Sort graph B/sub n/ is bipancyclic for n/spl ges/ 4, and also show that it is edge-bipancyclic for n/spl ges/5. To obtain this results, we also prove that we can construct a hamiltonian cycle of B/sub n/ that contains given two nonadjacent edges. Assume that F is the subset of E(B/sub n/). We prove that B/sub n /-F is bipancyclic whenever n /spl ges/4 and |F|/spl les/ n-3. Since B/sub n/ is a (n-1)-regular graph, this result is optimal in the worst case.
Shiying Wang - One of the best experts on this subject based on the ideXlab platform.
-
the 3 good neighbor connectivity of modified Bubble Sort graphs
Mathematical Problems in Engineering, 2020Co-Authors: Yanling Wang, Shiying WangAbstract:Let be a connected graph. A subset is called a - good-neighbor cut if is disconnected and each vertex of has at least neighbors. The - good-neighbor connectivity of is the minimum cardinality of - good-neighbor cuts. The - dimensional modified Bubble-Sort graph is a special Cayley graph. It has many good properties. In this paper, we prove that the 3-good-neighbor connectivity of is for .
-
diagnosability of Bubble Sort star graphs with missing edges
Journal of Interconnection Networks, 2019Co-Authors: Shiying Wang, Yingying WangAbstract:The diagnosability of a multiprocessor system plays an important role. The Bubble-Sort star graph BSn has many good properties. In this paper, we study the diagnosis on BSn under the comparison mod...
-
the g good neighbor diagnosability of Bubble Sort graphs under preparata metze and chien s pmc model and maeng and malek s mm model
Information-an International Interdisciplinary Journal, 2019Co-Authors: Shiying Wang, Zhenhua WangAbstract:Diagnosability of a multiprocessor system is an important topic of study. A measure for fault diagnosis of the system restrains that every fault-free node has at least g fault-free neighbor vertices, which is called the g-good-neighbor diagnosability of the system. As a famous topology structure of interconnection networks, the n-dimensional Bubble-Sort graph B n has many good properties. In this paper, we prove that (1) the 1-good-neighbor diagnosability of B n is 2 n − 3 under Preparata, Metze, and Chien’s (PMC) model for n ≥ 4 and Maeng and Malek’s (MM) ∗ model for n ≥ 5 ; (2) the 2-good-neighbor diagnosability of B n is 4 n − 9 under the PMC model and the MM ∗ model for n ≥ 4 ; (3) the 3-good-neighbor diagnosability of B n is 8 n − 25 under the PMC model and the MM ∗ model for n ≥ 7 .
-
the nature diagnosability of Bubble Sort star graphs under the pmc model and mm model
International Journal of Engineering and Applied Sciences, 2017Co-Authors: Mujiangshan Wang, Yuqing Lin, Shiying WangAbstract:Many multiprocessor systems have interconnection networks as underlying topologies and an interconnection network is usually represented by a graph where nodes represent processors and links represent communication links between processors. No fault set can contain all the neighbors of any fault-free vertex in the system, which is called the nature diagnosability of the system. Diagnosability of a multiprocessor system is one important study topic. As a famous topology structure of interconnection networks, the -dimensionalnbsp Bubble-Sort star graph nbsphas many good properties. In this paper, we prove that the nature diagnosability of nbspis nbspunder the PMC model for , the nature diagnosability of nbspis nbspunder the MM model for .
-
the 2 good neighbor connectivity and 2 good neighbor diagnosability of Bubble Sort star graph networks
Discrete Applied Mathematics, 2017Co-Authors: Shiying Wang, Zhenhua Wang, Mujiangshan WangAbstract:Connectivity plays an important role in measuring the fault tolerance of interconnection networks. The g -good-neighbor connectivity of an interconnection network G is the minimum cardinality of g -good-neighbor cuts. Diagnosability of a multiprocessor system is one important study topic. A new measure for fault diagnosis of the system restrains that every fault-free node has at least g fault-free neighbor vertices, which is called the g -good-neighbor diagnosability of the system. As a famous topology structure of interconnection networks, the n -dimensional Bubble-Sort star graph B S n has many good properties. In this paper, we prove that 2-good-neighbor connectivity of B S n is 8 n - 22 for n ź 5 and the 2 -good-neighbor connectivity of B S 4 is 8; the 2 -good-neighbor diagnosability of B S n is 8 n - 19 under the PMC model and MM ź model for n ź 5 .
Guo Jia - One of the best experts on this subject based on the ideXlab platform.
-
Edge-fault-tolerant strong Menger edge connectivity of Bubble-Sort star graphs
2020Co-Authors: Guo JiaAbstract:The connectivity and edge connectivity of interconnection network determine the fault tolerance of the network. An interconnection network is usually viewed as a connected graph, where vertex corresponds processor and edge corresponds link between two distinct processors. Given a connected graph $G$ with vertex set $V(G)$ and edge set $E(G)$, if for any two distinct vertices $u,v\in V(G)$, there exist $\min\{d_G(u),d_G(v)\}$ edge-disjoint paths between $u$ and $v$, then $G$ is strongly Menger edge connected. Let $m$ be an integer with $m\geq1$. If $G-F_e$ remains strongly Menger edge connected for any $F_e\subseteq E(G)$ with $|F_e|\leq m$, then $G$ is $m$-edge-fault-tolerant strongly Menger edge connected. If $G-F_e$ is strongly Menger edge connected for any $F_e\subseteq E(G)$ with $|F_e|\leq m$ and $\delta(G-F_e)\geq2$, then $G$ is $m$-conditional edge-fault-tolerant strongly Menger edge connected. In this paper, we consider the $n$-dimensional Bubble-Sort star graph $BS_n$. We show that $BS_n$ is $(2n-5)$-edge-fault-tolerant strongly Menger edge connected for $n\geq3$ and $(6n-17)$-conditional edge-fault-tolerant strongly Menger edge connected for $n\geq4$. Moreover, we give some examples to show that our results are optimal.Comment: 19 pages, 3 figure
-
Matching preclusion and strong matching preclusion of the Bubble-Sort star graphs
2020Co-Authors: Wang Xin, Ma Chaoqun, Guo JiaAbstract:Since a plurality of processors in a distributed computer system working in parallel, to ensure the fault tolerance and stability of the network is an important issue in distributed systems. As the topology of the distributed network can be modeled as a graph, the (strong) matching preclusion in graph theory can be used as a robustness measure for missing edges in parallel and distributed networks, which is defined as the minimum number of (vertices and) edges whose deletion results in the remaining network that has neither a perfect matching nor an almost-perfect matching. The Bubble-Sort star graph is one of the validly discussed interconnection networks related to the distributed systems. In this paper, we show that the strong matching preclusion number of an $n$-dimensional Bubble-Sort star graph $BS_n$ is $2$ for $n\geq3$ and each optimal strong matching preclusion set of $BS_n$ is a set of two vertices from the same bipartition set. Moreover, we show that the matching preclusion number of $BS_n$ is $2n-3$ for $n\geq3$ and that every optimal matching preclusion set of $BS_n$ is trivial.Comment: 12 pages, 5 figure
