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 super edge-connectivity of a graph is an important parameter to measure fault-tolerance of interconnection networks.This note shows that the Kautz undirected graph is super edge-connected,and provides a short proo...The super edge-connectivity of a graph is an important parameter to measure fault-tolerance of interconnection networks.This note shows that the Kautz undirected graph is super edge-connected,and provides a short proof of Lü and Zhang's result on super edge-connectivity of the de Bruijn undirected graph.展开更多
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].展开更多
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.展开更多
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.展开更多
With the vigorous development of mobile networks,the number of devices at the network edge is growing rapidly and the massive amount of data generated by the devices brings a huge challenge of response latency and com...With the vigorous development of mobile networks,the number of devices at the network edge is growing rapidly and the massive amount of data generated by the devices brings a huge challenge of response latency and communication burden.Existing resource monitoring systems are widely deployed in cloud data centers,but it is difficult for traditional resource monitoring solutions to handle the massive data generated by thousands of edge devices.To address these challenges,we propose a super resolution sensing(SRS)method for distributed resource monitoring,which can be used to recover reliable and accurate high‑frequency data from low‑frequency sampled resource monitoring data.Experiments based on the proposed SRS model are also conducted and the experimental results show that it can effectively reduce the errors generated when recovering low‑frequency monitoring data to high‑frequency data,and verify the effectiveness and practical value of applying SRS method for resource monitoring on edge clouds.展开更多
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.
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.展开更多
Let G be a connected graph with order n,minimum degree δ = δ（G） and edge-connectivity λ =λ（G）. A graph G is maximally edge-connected if λ = δ, and super edge-connected if every minimum edgecut consists of ed...Let G be a connected graph with order n,minimum degree δ = δ（G） and edge-connectivity λ =λ（G）. A graph G is maximally edge-connected if λ = δ, and super edge-connected if every minimum edgecut consists of edges incident with a vertex of minimum degree. Define the zeroth-order general Randic index R_α-0（G） =Σ x∈V（G） d_G-α（x）, where dG（x） denotes the degree of the vertex x. In this paper, we present two sufficient conditions for graphs and triangle-free graphs to be super edge-connected in terms of the zeroth-order general Randic index for -1 ≤α 〈 0, respectively.展开更多
Let G be a connected graph with vertex-set V(G)and edge-set E(G).A subset F of E(G)is an s-restricted edge-cut of G if G-F is disconnected and every component of G-F has at least s vertices.Letλs(G)be the minimum siz...Let G be a connected graph with vertex-set V(G)and edge-set E(G).A subset F of E(G)is an s-restricted edge-cut of G if G-F is disconnected and every component of G-F has at least s vertices.Letλs(G)be the minimum size of all s-restricted edge-cuts of G andξs(G)=min{|[X,V(G)\X]|:|X|=s,G[X]is connected},where[X,V(G)\X]is the set of edges with exactly one end in X.A graph G with an s-restricted edge-cut is called super s-restricted edge-connected,in short super-λs,ifλs(G)=ξs(G)and every minimum s-restricted edge-cut of G isolates one component G[X]with|X|=s.It is proved in this paper that a connected vertex-transitive graph G with degree k>5 and girth g>5 is super-λs for any positive integer s with s 2g or s 10 if k=g=6.展开更多
A graph G is super-edge-connected,for short super-λ,if every minimum edge-cut consists of edges adjacent to a vertex of minimum degree.Alphabet overlap graph G（k,d,s）is undirected,simple graph with vertex set V={v...A graph G is super-edge-connected,for short super-λ,if every minimum edge-cut consists of edges adjacent to a vertex of minimum degree.Alphabet overlap graph G（k,d,s）is undirected,simple graph with vertex set V={v｜v=1（）kv…v;vi∈{1,2,…,d},i=1,…,k}.Two vertices u=（u1…uk）and v=（v1…vk）are adjacent if and only if us＋i=vi or vs＋i=ui（i=1,…,k-s）.In particular G（k,d,1）is just an undirected de Bruijn graph.In this paper,we show that the diameter of G（k,d,s）is k s,the girth is 3.Finally,we prove that G（k,d,s）（s≥k/2）is super-λ.展开更多
基金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.
基金by ANSF( 0 1 0 4 61 0 2 ) and the National Natural Science Foundatim of China ( 1 0 2 71 1 1 4)
文摘The super edge-connectivity of a graph is an important parameter to measure fault-tolerance of interconnection networks.This note shows that the Kautz undirected graph is super edge-connected,and provides a short proof of Lü and Zhang's result on super edge-connectivity of the de Bruijn undirected graph.
基金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].
文摘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.
文摘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.
文摘With the vigorous development of mobile networks,the number of devices at the network edge is growing rapidly and the massive amount of data generated by the devices brings a huge challenge of response latency and communication burden.Existing resource monitoring systems are widely deployed in cloud data centers,but it is difficult for traditional resource monitoring solutions to handle the massive data generated by thousands of edge devices.To address these challenges,we propose a super resolution sensing(SRS)method for distributed resource monitoring,which can be used to recover reliable and accurate high‑frequency data from low‑frequency sampled resource monitoring data.Experiments based on the proposed SRS model are also conducted and the experimental results show that it can effectively reduce the errors generated when recovering low‑frequency monitoring data to high‑frequency data,and verify the effectiveness and practical value of applying SRS method for resource monitoring on edge clouds.
文摘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.
基金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.
基金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.
基金supported by the National Natural Science Foundation of China(No.11501490,61373019,11371307)by the Natural Science Foundation of Shandong Province(No.ZR2015AM006)
文摘Let G be a connected graph with order n,minimum degree δ = δ（G） and edge-connectivity λ =λ（G）. A graph G is maximally edge-connected if λ = δ, and super edge-connected if every minimum edgecut consists of edges incident with a vertex of minimum degree. Define the zeroth-order general Randic index R_α-0（G） =Σ x∈V（G） d_G-α（x）, where dG（x） denotes the degree of the vertex x. In this paper, we present two sufficient conditions for graphs and triangle-free graphs to be super edge-connected in terms of the zeroth-order general Randic index for -1 ≤α 〈 0, respectively.
基金supported by National Natural Science Foundation of China(Grant No.61073046)
文摘Let G be a connected graph with vertex-set V(G)and edge-set E(G).A subset F of E(G)is an s-restricted edge-cut of G if G-F is disconnected and every component of G-F has at least s vertices.Letλs(G)be the minimum size of all s-restricted edge-cuts of G andξs(G)=min{|[X,V(G)\X]|:|X|=s,G[X]is connected},where[X,V(G)\X]is the set of edges with exactly one end in X.A graph G with an s-restricted edge-cut is called super s-restricted edge-connected,in short super-λs,ifλs(G)=ξs(G)and every minimum s-restricted edge-cut of G isolates one component G[X]with|X|=s.It is proved in this paper that a connected vertex-transitive graph G with degree k>5 and girth g>5 is super-λs for any positive integer s with s 2g or s 10 if k=g=6.
文摘A graph G is super-edge-connected,for short super-λ,if every minimum edge-cut consists of edges adjacent to a vertex of minimum degree.Alphabet overlap graph G（k,d,s）is undirected,simple graph with vertex set V={v｜v=1（）kv…v;vi∈{1,2,…,d},i=1,…,k}.Two vertices u=（u1…uk）and v=（v1…vk）are adjacent if and only if us＋i=vi or vs＋i=ui（i=1,…,k-s）.In particular G（k,d,1）is just an undirected de Bruijn graph.In this paper,we show that the diameter of G（k,d,s）is k s,the girth is 3.Finally,we prove that G（k,d,s）（s≥k/2）is super-λ.
