Let h be a nonnegative integer. The h-restricted edge connectivity λ h(G) of a simple connected graph G is defined as the minimum cardinality over the sets of edges of G, if any, whose removal disconnects G and every...Let h be a nonnegative integer. The h-restricted edge connectivity λ h(G) of a simple connected graph G is defined as the minimum cardinality over the sets of edges of G, if any, whose removal disconnects G and every component of the resulting graph has more than h vertices. This paper gave a necessary and sufficient condition and also three useful sufficient conditions to guarantee the existence of λ h(G). Moreover, it explicitly characterized the graphs whose 2-restricted edge connectivities do not exist.展开更多
The classical hypercube structure is a popular topological architecture in parallel computing environments and a large number of variations based on the hypercube were posed in the past three decades. Reliability eval...The classical hypercube structure is a popular topological architecture in parallel computing environments and a large number of variations based on the hypercube were posed in the past three decades. Reliability evaluation of systems is important to the design and maintenance of multiprocessor systems. The h-extra edge-connectivity of graph G（V, E） is a kind of measure for the reliability of interconnection systems, which is defined as the minimum cardinality of a subset of edge set, if any, whose deletion disconnects G and such that every re- maining component has at least h vertices. This paper shows that the h-extra edge-connectivity 2n-1 2n-1 of the hypercube Qn is a constant 2n-1 for 2n-1/3≤ h2n-1, and n ≥ 4, which extends the result of [Bounding the size of the subgraph induced by m vertices and extra edge-connectivity of hypercubes, Discrete Applied Mathematics, 2013, 161（16）： 2753-2757].展开更多
Identifying important nodes and edges in complex networks has always been a popular research topic in network science and also has important implications for the protection of real-world complex systems.Finding the cr...Identifying important nodes and edges in complex networks has always been a popular research topic in network science and also has important implications for the protection of real-world complex systems.Finding the critical structures in a system allows us to protect the system from attacks or failures with minimal cost.To date,the problem of identifying critical nodes in networks has been widely studied by many scholars,and the theory is becoming increasingly mature.However,there is relatively little research related to edges.In fact,critical edges play an important role in maintaining the basic functions of the network and keeping the integrity of the structure.Sometimes protecting critical edges is less costly and more flexible in operation than just focusing on nodes.Considering the integrity of the network topology and the propagation dynamics on it,this paper proposes a centrality measure based on the number of high-order structural overlaps in the first and second-order neighborhoods of edges.The effectiveness of the metric is verified by the infection-susceptibility(SI)model,the robustness index R,and the number of connected branchesθ.A comparison is made with three currently popular edge importance metrics from two synthetic and four real networks.The simulation results show that the method outperforms existing methods in identifying critical edges that have a significant impact on both network connectivity and propagation dynamics.At the same time,the near-linear time complexity can be applied to large-scale networks.展开更多
An approximation algorithm is presented for augmenting an undirected weightedgraph to a K-edge-connected graph.The algorithm is useful for designing a reliable network.
Tian and Meng in [Y. Tian and J. Meng, λc -Optimally half vertex transitive graphs with regularity k, Information Processing Letters 109 (2009) 683 - 686] shown that a connected half vertex transitive graph with regu...Tian and Meng in [Y. Tian and J. Meng, λc -Optimally half vertex transitive graphs with regularity k, Information Processing Letters 109 (2009) 683 - 686] shown that a connected half vertex transitive graph with regularity k and girth g(G) ≥ 6 is cyclically optimal. In this paper, we show that a connected half vertex transitive graph G is super cyclically edge-connected if minimum degree δ(G) ≥ 6 and girth g(G) ≥ 6.展开更多
Bollobas and Gyarfas conjectured that for n 〉 4（k - 1） every 2-edge-coloring of Kn contains a monochromatic k-connected subgraph with at least n - 2k ＋ 2 vertices. Liu, et al. proved that the conjecture holds when...Bollobas and Gyarfas conjectured that for n 〉 4（k - 1） every 2-edge-coloring of Kn contains a monochromatic k-connected subgraph with at least n - 2k ＋ 2 vertices. Liu, et al. proved that the conjecture holds when n 〉 13k - 15. In this note, we characterize all the 2-edge-colorings of Kn where each monochromatic k-connected subgraph has at most n - 2k ＋ 2 vertices for n ≥ 13k - 15.展开更多
The P_(k)-path graph P_(k)(G)corresponding to a graph G has for vertices the set of all paths of length k in G.Two vertices are joined by an edge if and only if the intersection of the corresponding paths forms a path...The P_(k)-path graph P_(k)(G)corresponding to a graph G has for vertices the set of all paths of length k in G.Two vertices are joined by an edge if and only if the intersection of the corresponding paths forms a path of length k-1 in G,and their union forms either a cycle or a path of length k+1.Let Ek={(v,p),p E V(P_(k)(G)),v is an end vertex of p in G},we define total P_(k)-graphs T_(k)(G)as Yk(G)=(V(G)UV(P_(k)(G)),E(G)U E(PI(G))U Ek).In this note,we introduce total P,-graphs Th(G)and study their edge connectivity,as the generaliza-tion of total graphs.展开更多
Let G be a k-regular connected graph of order at least six. If G has girth three, its 3-restricted edge connectivity λ3(G) ≤3k-6. The equality holds when G is a cubic or 4-regular connected vertex-transitive graph w...Let G be a k-regular connected graph of order at least six. If G has girth three, its 3-restricted edge connectivity λ3(G) ≤3k-6. The equality holds when G is a cubic or 4-regular connected vertex-transitive graph with the only exception that G is a 4-regular graph with λ3(G) = 4. Furthermore, λ3(G) = 4 if and only if G contains K4 as its subgraph.展开更多
基金National Natural Science Foundation of China( No.199710 5 6)
文摘Let h be a nonnegative integer. The h-restricted edge connectivity λ h(G) of a simple connected graph G is defined as the minimum cardinality over the sets of edges of G, if any, whose removal disconnects G and every component of the resulting graph has more than h vertices. This paper gave a necessary and sufficient condition and also three useful sufficient conditions to guarantee the existence of λ h(G). Moreover, it explicitly characterized the graphs whose 2-restricted edge connectivities do not exist.
基金Supported by the National Natural Science Foundation of China(11171283,11471273,11461038,11301440)Natural Sciences Foundation of Shanxi Province(2014021010-2)
文摘The classical hypercube structure is a popular topological architecture in parallel computing environments and a large number of variations based on the hypercube were posed in the past three decades. Reliability evaluation of systems is important to the design and maintenance of multiprocessor systems. The h-extra edge-connectivity of graph G（V, E） is a kind of measure for the reliability of interconnection systems, which is defined as the minimum cardinality of a subset of edge set, if any, whose deletion disconnects G and such that every re- maining component has at least h vertices. This paper shows that the h-extra edge-connectivity 2n-1 2n-1 of the hypercube Qn is a constant 2n-1 for 2n-1/3≤ h2n-1, and n ≥ 4, which extends the result of [Bounding the size of the subgraph induced by m vertices and extra edge-connectivity of hypercubes, Discrete Applied Mathematics, 2013, 161（16）： 2753-2757].
文摘Identifying important nodes and edges in complex networks has always been a popular research topic in network science and also has important implications for the protection of real-world complex systems.Finding the critical structures in a system allows us to protect the system from attacks or failures with minimal cost.To date,the problem of identifying critical nodes in networks has been widely studied by many scholars,and the theory is becoming increasingly mature.However,there is relatively little research related to edges.In fact,critical edges play an important role in maintaining the basic functions of the network and keeping the integrity of the structure.Sometimes protecting critical edges is less costly and more flexible in operation than just focusing on nodes.Considering the integrity of the network topology and the propagation dynamics on it,this paper proposes a centrality measure based on the number of high-order structural overlaps in the first and second-order neighborhoods of edges.The effectiveness of the metric is verified by the infection-susceptibility(SI)model,the robustness index R,and the number of connected branchesθ.A comparison is made with three currently popular edge importance metrics from two synthetic and four real networks.The simulation results show that the method outperforms existing methods in identifying critical edges that have a significant impact on both network connectivity and propagation dynamics.At the same time,the near-linear time complexity can be applied to large-scale networks.
文摘An approximation algorithm is presented for augmenting an undirected weightedgraph to a K-edge-connected graph.The algorithm is useful for designing a reliable network.
文摘Tian and Meng in [Y. Tian and J. Meng, λc -Optimally half vertex transitive graphs with regularity k, Information Processing Letters 109 (2009) 683 - 686] shown that a connected half vertex transitive graph with regularity k and girth g(G) ≥ 6 is cyclically optimal. In this paper, we show that a connected half vertex transitive graph G is super cyclically edge-connected if minimum degree δ(G) ≥ 6 and girth g(G) ≥ 6.
基金Supported by the National Natural Science Foundation of China(10701065 and 11101378)Zhejiang Provincial Natural Science Foundation(LY14A010009)
文摘Bollobas and Gyarfas conjectured that for n 〉 4（k - 1） every 2-edge-coloring of Kn contains a monochromatic k-connected subgraph with at least n - 2k ＋ 2 vertices. Liu, et al. proved that the conjecture holds when n 〉 13k - 15. In this note, we characterize all the 2-edge-colorings of Kn where each monochromatic k-connected subgraph has at most n - 2k ＋ 2 vertices for n ≥ 13k - 15.
基金supported by Natural Sciences Foundation of Guangxi Province(2012GXNSFBA053005)
文摘The P_(k)-path graph P_(k)(G)corresponding to a graph G has for vertices the set of all paths of length k in G.Two vertices are joined by an edge if and only if the intersection of the corresponding paths forms a path of length k-1 in G,and their union forms either a cycle or a path of length k+1.Let Ek={(v,p),p E V(P_(k)(G)),v is an end vertex of p in G},we define total P_(k)-graphs T_(k)(G)as Yk(G)=(V(G)UV(P_(k)(G)),E(G)U E(PI(G))U Ek).In this note,we introduce total P,-graphs Th(G)and study their edge connectivity,as the generaliza-tion of total graphs.
基金Acknowledgements： The project is supported by the National Natural Science Foundation of China （No. 40471101） and Research Foundation of Nanjing University of Information Science and Technology.
文摘Let G be a k-regular connected graph of order at least six. If G has girth three, its 3-restricted edge connectivity λ3(G) ≤3k-6. The equality holds when G is a cubic or 4-regular connected vertex-transitive graph with the only exception that G is a 4-regular graph with λ3(G) = 4. Furthermore, λ3(G) = 4 if and only if G contains K4 as its subgraph.
