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].展开更多
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.展开更多
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.展开更多
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.展开更多
An m-restricted edge cut is an edge cut that separates a connected graph into a disconnected one with no components having order less than m. m-restricted edge connectivity λ<SUB> m </SUB>is the c...An m-restricted edge cut is an edge cut that separates a connected graph into a disconnected one with no components having order less than m. m-restricted edge connectivity λ<SUB> m </SUB>is the cardinality of a minimum m-restricted edge cut. Let G be a connected k-regular graph of order at least 2m that contains m-restricted edge cuts and X be a subgraph of G. Let ∂(X) denote the number of edges with one end in X and the other not in X and ξ<SUB> m </SUB>= min{∂(X) : X is a connected vertex-induced subgraph of order m}. It is proved in this paper that if G has girth at least m/2+ 2, then λ<SUB> m </SUB>≤ ξ<SUB> m </SUB>. The upper bound of λ<SUB> m </SUB>is sharp.展开更多
Intelligent and connected vehicles have leveraged edge computing paradigm to enhance their environment comprehension and behavior planning capabilities.As the quantity of intelligent vehicles and the demand for edge c...Intelligent and connected vehicles have leveraged edge computing paradigm to enhance their environment comprehension and behavior planning capabilities.As the quantity of intelligent vehicles and the demand for edge computing are increasing rapidly,it becomes critical to efficiently orchestrate the communication and computation resources on edge clouds.Existing methods usually perform resource allocation in a fairly effective but still reactive manner,which is subject to the capacity of nearby edge clouds.To deal with the contradiction between the spatiotemporally varying demands for edge computing and the fixed edge cloud capacity,we proactively balance the edge computing demands across edge clouds by appropriate route planning.In this paper,route planning and resource allocation are jointly optimized to enhance intelligent driving.We propose a multi-scale decentralized optimization method to deal with the curse of dimensionality.In large-scale optimization,backpressure algorithm is used to conduct route planning and load balancing across edge clouds.In small-scale optimization,game-theoretic multi-agent learning is exploited to perform regional resource allocation.The experimental results show that the proposed algorithm outperforms the baseline algorithms which optimize route planning and resource allocation separately.展开更多
Let G be a simple connected graph of order n ≥ 6. The third edge-connectivity of G is defined as the minimum cardinality over all the sets of edges, if any, whose deletion disconnects G and every component of the res...Let G be a simple connected graph of order n ≥ 6. The third edge-connectivity of G is defined as the minimum cardinality over all the sets of edges, if any, whose deletion disconnects G and every component of the resulting graph has at least 3 vertices. In this paper, we first characterize those graphs whose third-edge connectivity is well defined,then establish the tight upper bound for the third edge-connectivity.展开更多
The k-component edgeconnectivity cλk(G)of anon-completegraph G is themini mum number of edges whose deletion results in a graph with at least k components In this paper,we extend some results by Guo et al.(Appl Math ...The k-component edgeconnectivity cλk(G)of anon-completegraph G is themini mum number of edges whose deletion results in a graph with at least k components In this paper,we extend some results by Guo et al.(Appl Math Comput 334:401-406,2018)by determining the component edge connectivity of the locally twisted cubes LTQn,i.e.,cλk+1(LTQn)=kn-exk/2for 1≤2[n/2],n≥7,where exk=∑si=0ti2ti+∑si=02·i·2ti,and k is a positive integer with decomposition k=∑si=02ti such that to="log2k"and ti="log2(k-∑i-1 r=02tr)"for i≥1.As a by-product,we characterize the corresponding optimal solutions.展开更多
The twisted cube TQn is a variant of the hypercube Qn. It has been shown by Chang, Wang and Hsu [Topological properties of twisted cube. Information Science, 113, 147-167 （1999）] that TQn contains a cycle of every l...The twisted cube TQn is a variant of the hypercube Qn. It has been shown by Chang, Wang and Hsu [Topological properties of twisted cube. Information Science, 113, 147-167 （1999）] that TQn contains a cycle of every length from 4 to 2^n. In this paper, we improve this result by showing that every edge of TQn lies on a cycle of every length from 4 to 2^n inclusive. We also show that the twisted cube are Hamiltonian connected.展开更多
The third edge-connectivity λ3(G) of a graph G is defined as the minimum cardinality over all sets of edges, if any, whose deletion disconnects G and each component of the resulting graph has at least 3 vertices. An ...The third edge-connectivity λ3(G) of a graph G is defined as the minimum cardinality over all sets of edges, if any, whose deletion disconnects G and each component of the resulting graph has at least 3 vertices. An upper bound has been established for λ3(G) whenever λ3(G) is well-defined. This paper first introduces two combinatorial optimization concepts, that is, maximality and superiority, of λ3(G), and then proves the Ore type sufficient conditions for G to be maximally and super third edge-connected. These concepts and results are useful in network reliability analysis.展开更多
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.展开更多
By Petersen＇s Theorem, a bridgeless cubic graph has a 2-factor. Fleischner （Discrete Math., 101, 33-37 （1992）） has extended this result to bridgeless graphs of minimum degree at least three by showing that every ...By Petersen＇s Theorem, a bridgeless cubic graph has a 2-factor. Fleischner （Discrete Math., 101, 33-37 （1992）） has extended this result to bridgeless graphs of minimum degree at least three by showing that every such graph has an even factor without isolated vertices. Let me〉 0 be even and mo〉 0 be odd. In this paper, we prove that every me-edge-connected graph with minimum degree at least me ＋ 1 contains an even factor with minimum degree at least me and every （mo ＋ 1）- edge-connected graph contains an odd factor with minimum degree at least too, which further extends Fleischner＇s result. Moreover, we show that our results are best possible.展开更多
Epilepsy is a transient neurological disorder associated with changes in the functional connections of the brain. Abnormal electrical discharges can be observed during an epileptic seizure. However, in the absence of ...Epilepsy is a transient neurological disorder associated with changes in the functional connections of the brain. Abnormal electrical discharges can be observed during an epileptic seizure. However, in the absence of an epileptic seizure, the anatomical structure of the brain and the electrical waves of the brain are not observed, making it difficult to explain the cause. This paper deals with together weighted imaging (DWI) sequence data in functional magnetic resonance imaging (FMRI) of epileptic patients before seizure, using Anatomical Automatic Labeling (AAL) template extracted 116 brain regions and the introduction of time series, a matrix of 116 × 116. Pearson correlation coefficient was calculated to investigate the pathological condition of brain function in epilepsy patients, using of neural network visualization system of innovative visual display and compared with the normal epileptic brain function to connect the image, with 38 cases of epilepsy by 187 cases of normal DWI experiment data, and can confirm the existence of brain function in patients with epilepsy connections. Cerebral neural network visualization system showed partial functional connection loss between frontal lobe and temporal lobe in epileptic group compared with normal control group.展开更多
基金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].
文摘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.
文摘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.
基金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.
基金National Natural Science Foundation of China (Grant No.10271105) and Doctoral Fund of Zhangzhou Normal College.
文摘An m-restricted edge cut is an edge cut that separates a connected graph into a disconnected one with no components having order less than m. m-restricted edge connectivity λ<SUB> m </SUB>is the cardinality of a minimum m-restricted edge cut. Let G be a connected k-regular graph of order at least 2m that contains m-restricted edge cuts and X be a subgraph of G. Let ∂(X) denote the number of edges with one end in X and the other not in X and ξ<SUB> m </SUB>= min{∂(X) : X is a connected vertex-induced subgraph of order m}. It is proved in this paper that if G has girth at least m/2+ 2, then λ<SUB> m </SUB>≤ ξ<SUB> m </SUB>. The upper bound of λ<SUB> m </SUB>is sharp.
基金supported in part by the Natural Science Foundation of China under Grant 61902035 and Grant 61876023in part by the Natural Science Foundation of Shandong Province of China under Grant ZR2020LZH005in part by China Postdoctoral Science Foundation under Grant 2019M660565.
文摘Intelligent and connected vehicles have leveraged edge computing paradigm to enhance their environment comprehension and behavior planning capabilities.As the quantity of intelligent vehicles and the demand for edge computing are increasing rapidly,it becomes critical to efficiently orchestrate the communication and computation resources on edge clouds.Existing methods usually perform resource allocation in a fairly effective but still reactive manner,which is subject to the capacity of nearby edge clouds.To deal with the contradiction between the spatiotemporally varying demands for edge computing and the fixed edge cloud capacity,we proactively balance the edge computing demands across edge clouds by appropriate route planning.In this paper,route planning and resource allocation are jointly optimized to enhance intelligent driving.We propose a multi-scale decentralized optimization method to deal with the curse of dimensionality.In large-scale optimization,backpressure algorithm is used to conduct route planning and load balancing across edge clouds.In small-scale optimization,game-theoretic multi-agent learning is exploited to perform regional resource allocation.The experimental results show that the proposed algorithm outperforms the baseline algorithms which optimize route planning and resource allocation separately.
基金This work was supported by Zhejiang Provincial Natural Science Foundation of China(Grant No.102055)the Natural Science Foundation of Zhejiang Normal UniversityThe second author was supported by the National Natural Science Foundation of China(Grant No.19971056).
文摘Let G be a simple connected graph of order n ≥ 6. The third edge-connectivity of G is defined as the minimum cardinality over all the sets of edges, if any, whose deletion disconnects G and every component of the resulting graph has at least 3 vertices. In this paper, we first characterize those graphs whose third-edge connectivity is well defined,then establish the tight upper bound for the third edge-connectivity.
基金the National Natural Science Foundation of China(No.11531011).
文摘The k-component edgeconnectivity cλk(G)of anon-completegraph G is themini mum number of edges whose deletion results in a graph with at least k components In this paper,we extend some results by Guo et al.(Appl Math Comput 334:401-406,2018)by determining the component edge connectivity of the locally twisted cubes LTQn,i.e.,cλk+1(LTQn)=kn-exk/2for 1≤2[n/2],n≥7,where exk=∑si=0ti2ti+∑si=02·i·2ti,and k is a positive integer with decomposition k=∑si=02ti such that to="log2k"and ti="log2(k-∑i-1 r=02tr)"for i≥1.As a by-product,we characterize the corresponding optimal solutions.
基金Supported by National Natural Science Foundation of China (Grant No. 10701074)Sciences Foundation for Young Scholars of Beijing Normal University and Priority Discipline of Beijing Normal University
文摘The twisted cube TQn is a variant of the hypercube Qn. It has been shown by Chang, Wang and Hsu [Topological properties of twisted cube. Information Science, 113, 147-167 （1999）] that TQn contains a cycle of every length from 4 to 2^n. In this paper, we improve this result by showing that every edge of TQn lies on a cycle of every length from 4 to 2^n inclusive. We also show that the twisted cube are Hamiltonian connected.
基金This work was supported by the National Natural Science Foundation of China(Grant No.10471131)the Natural Science Foundation of Zhejiang Province(Grant No.102055).
文摘The third edge-connectivity λ3(G) of a graph G is defined as the minimum cardinality over all sets of edges, if any, whose deletion disconnects G and each component of the resulting graph has at least 3 vertices. An upper bound has been established for λ3(G) whenever λ3(G) is well-defined. This paper first introduces two combinatorial optimization concepts, that is, maximality and superiority, of λ3(G), and then proves the Ore type sufficient conditions for G to be maximally and super third edge-connected. These concepts and results are useful in network reliability analysis.
基金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 Nos.11471257 and 11101329)
文摘By Petersen＇s Theorem, a bridgeless cubic graph has a 2-factor. Fleischner （Discrete Math., 101, 33-37 （1992）） has extended this result to bridgeless graphs of minimum degree at least three by showing that every such graph has an even factor without isolated vertices. Let me〉 0 be even and mo〉 0 be odd. In this paper, we prove that every me-edge-connected graph with minimum degree at least me ＋ 1 contains an even factor with minimum degree at least me and every （mo ＋ 1）- edge-connected graph contains an odd factor with minimum degree at least too, which further extends Fleischner＇s result. Moreover, we show that our results are best possible.
文摘Epilepsy is a transient neurological disorder associated with changes in the functional connections of the brain. Abnormal electrical discharges can be observed during an epileptic seizure. However, in the absence of an epileptic seizure, the anatomical structure of the brain and the electrical waves of the brain are not observed, making it difficult to explain the cause. This paper deals with together weighted imaging (DWI) sequence data in functional magnetic resonance imaging (FMRI) of epileptic patients before seizure, using Anatomical Automatic Labeling (AAL) template extracted 116 brain regions and the introduction of time series, a matrix of 116 × 116. Pearson correlation coefficient was calculated to investigate the pathological condition of brain function in epilepsy patients, using of neural network visualization system of innovative visual display and compared with the normal epileptic brain function to connect the image, with 38 cases of epilepsy by 187 cases of normal DWI experiment data, and can confirm the existence of brain function in patients with epilepsy connections. Cerebral neural network visualization system showed partial functional connection loss between frontal lobe and temporal lobe in epileptic group compared with normal control group.
