A path in an edge-colored graph G is called a rainbow path if no two edges of the path are colored the same color.The minimum number of colors required to color the edges of G such that every pair of vertices are conn...A path in an edge-colored graph G is called a rainbow path if no two edges of the path are colored the same color.The minimum number of colors required to color the edges of G such that every pair of vertices are connec ted by at least k internally ver tex-disjoint rainbow paths is called the rainbow k-connectivity of the graph G,denoted by rck(G).For the random graph G(n,p),He and Liang got a sharp threshold function for the property rck(G(n,p))≤d.For the random equi-bipartite graph G(n,n,p),Fujita et.al.got a sharp threshold function for the property rck(G(n,n,p))≤3.They also posed the following problem:For d≥2,determine a sharp threshold function for the property rck(G)≤d,where G is another random graph model.This paper is to give a solution to their problem in the general random bipartite graph model G(m,n,p).展开更多
A graph G possesses Hamiltonian s-properties when G is Hamilton-connected if s=1,Hamiltonian if s=0,and traceable if s=-1.Let S_A(G)=λ_n(G)-λ_1(G)and S_L(G)=μ_n(G)-μ_2(G)be the spread and the Laplacian spread of G...A graph G possesses Hamiltonian s-properties when G is Hamilton-connected if s=1,Hamiltonian if s=0,and traceable if s=-1.Let S_A(G)=λ_n(G)-λ_1(G)and S_L(G)=μ_n(G)-μ_2(G)be the spread and the Laplacian spread of G,respectively,whereλ_n(G)andλ_1(G)are the largest and smallest eigenvalues of G,andμ_n(G)andμ_2(G)are the largest and second smallest Laplacian eigenvalues of G,respectively.In this paper,we shall present two sufficient conditions involving S_A(G)and S_L(G)for a k-connected graph to possess Hamiltonian s-properties,respectively.We also derive a sufficient condition on the Laplacian eigenratio μ2(G)/μ(G) for a k-connected graph to possess Hamiltonian s-properties.展开更多
Let G be a k-connected graph, and T be a subset of V（G）. If G-T is not connected,then T is said to be a cut-set of G. A k-cut-set T of G is a cut-set of G with │T│=k. Let T bea k-cut-set of a k-connected graph G. ...Let G be a k-connected graph, and T be a subset of V（G）. If G-T is not connected,then T is said to be a cut-set of G. A k-cut-set T of G is a cut-set of G with │T│=k. Let T bea k-cut-set of a k-connected graph G. If G - T can be partitioned into subgraphs G1 and G2such that │G1│≥ 2, │G2│ 〉 2, then we call T a nontrivial k-cut-set of G. Suppose that G is a（k-1）-connected graph without nontrivial （k - 1）-cut-set. Then we call G a quasi k-connectedgraph. In this paper, we prove that for any integer k ≥ 5, if G is a k-connected graph withoutK4-, then every vertex of G is incident with an edge whose contraction yields a quasi k-connectedgraph, and so there are at least │V（G）│/2 edges of G such that the contraction of every member ofthem results in a quasi k-connected graph.展开更多
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.展开更多
This paper proposes k-regular and k-connected(k&k) structure against multifaults in ultra-high capacity optical networks.Theoretical results show that pre-configured k&k structure can reach the lower bound on ...This paper proposes k-regular and k-connected(k&k) structure against multifaults in ultra-high capacity optical networks.Theoretical results show that pre-configured k&k structure can reach the lower bound on logical redundancy.The switching time of k&k protection structure is as quickly as ringbased protection in SDH network.It is the optimal protection structure in ultra-high capacity optical networks against multi-faults.We develop the linear programming model for k&k structure and propose a construction method for k&k structure design.Simulations are conducted for spare spectrum resources effi ciency of the pre-confi gured k&k structure under multi-faults on representative COST239 and NSFnet topologies.Numerical results show that the spare spectrum resources efficiency of k&k structure can reach the lower bound on logical redundancy in static networks.And it can largely improve spare spectrum resources effi ciency compared with p-cycles based protection structure without reducing protection effi ciency under dynamic traffi cs.展开更多
Let G be a graph on n vertices whose degree sequence is d_(1)≥…≥d_(n).For a positive integer p,the degree power of G is defined by e_p(G)=∑_(i=1)^(n) d_(i)^(p).In this paper,by majorization,we prove that for a min...Let G be a graph on n vertices whose degree sequence is d_(1)≥…≥d_(n).For a positive integer p,the degree power of G is defined by e_p(G)=∑_(i=1)^(n) d_(i)^(p).In this paper,by majorization,we prove that for a minimally k-connected graph G of order n≥4k,it always holds e_(2)(G)≤kn(n-k)and the extremal graph is K_(k,n-k).Furthermore,we respectively determine the maximum degree powers among all minimally 2(3)-connected graphs and minimally 2-edgeconnected graphs,whose extremal graphs are also characterized.展开更多
One of the fundamental properties of an ad hoc network is its connectivity. Maintaining connectivity in wireless networks is extremely difficult due to dynamic changing topology of MANETs. There are several techniques...One of the fundamental properties of an ad hoc network is its connectivity. Maintaining connectivity in wireless networks is extremely difficult due to dynamic changing topology of MANETs. There are several techniques to understand the connectivity level for a given network topology. In this paper, we examine the existing methods and discuss the issues and challenges that are still insurmountable in order to enhance the connectivity properties of wireless multi hop networks.展开更多
In Wireless Sensor Network(WSN),coverage and connectivity are the vital challenges in the target-based region.The linear objective is to find the positions to cover the complete target nodes and connectivity between e...In Wireless Sensor Network(WSN),coverage and connectivity are the vital challenges in the target-based region.The linear objective is to find the positions to cover the complete target nodes and connectivity between each sensor for data forwarding towards the base station given a grid with target points and a potential sensor placement position.In this paper,a multiobjective problem on target-based WSN(t-WSN)is derived,which minimizes the number of deployed nodes,and maximizes the cost of coverage and sensing range.An Evolutionary-based Non-Dominated Sorting Genetic Algorithm-II(NSGA-II)is incorporated to tackle this multiobjective problem efficiently.Multiobjective problems are intended to solve different objectives of a problem simultaneously.Bio-inspired algorithms address the NP-hard problem most effectively in recent years.In NSGA-II,the Non-Dominated sorting preserves the better solution in different objectives simultaneously using dominance relation.In the diversity maintenance phase,density estimation and crowd comparison are the two components that balance the exploration and exploitation phase of the algorithm.Performance of NSGA-II on this multiobjective problem is evaluated in terms of performance indicators Overall Non-dominated Vector Generation(ONGV)and Spacing(SP).The simulation results show the proposed method performs outperforms the existing algorithms in different aspects of the model.展开更多
The generalized kt-connectivity K(k)(G)and k-edge-connectivityλ_(k)(G)of a graph G are a natural generalization of traditional connectivity K(G)and edge connectivityλ(G),respectively,which for K(G)=K_(2)(G)andλ(G)=...The generalized kt-connectivity K(k)(G)and k-edge-connectivityλ_(k)(G)of a graph G are a natural generalization of traditional connectivity K(G)and edge connectivityλ(G),respectively,which for K(G)=K_(2)(G)andλ(G)=λ_(2)(G).They are important parameters which can often be used to measure the reliability and fault tolerance of interconnection networks.CRNs is a new family of composite networks based on the complete graph,which contain common networks and have the same structural properties as alter-nating group network,and may also include some unknown networks.In this paper,we investigate the generalized 3-connectivity and 3-edge-connectivity of CRNs,and show that K_(3)(G_(l),m)=λ_(3)(G_(l)m)=m-2.展开更多
An edge e of a k-connected graph G is said to be a removable edge if G e is still kconnected, where G e denotes the graph obtained from G by deleting e to get G - e, and for any end vertex of e with degree k - 1 in ...An edge e of a k-connected graph G is said to be a removable edge if G e is still kconnected, where G e denotes the graph obtained from G by deleting e to get G - e, and for any end vertex of e with degree k - 1 in G - e, say x, delete x, and then add edges between any pair of non-adjacent vertices in NG-e（x）. The existence of removable edges of k-connected graphs and some properties of 3-connected graphs and 4-connected graphs have been investigated. In the present paper, we investigate some properties of k-connected graphs and study the distribution of removable edges on a cycle in a k-connected graph （k ≥ 4）.展开更多
An edge e of a k-connected graph G is said to be a removable edge if G O e is still k-connected, where G O e denotes the graph obtained from G by the following way： deleting e to get G - e, and for any end vertex of ...An edge e of a k-connected graph G is said to be a removable edge if G O e is still k-connected, where G O e denotes the graph obtained from G by the following way： deleting e to get G - e, and for any end vertex of e with degree k - 1 in G - e, say x, deleting x, and then adding edges between any pair of non-adjacent vertices in NG-e （x）. The existence of removable edges of k-connected graphs and some properties of k-connected graphs have been investigated. In the present paper, we investigate the distribution of removable edges on a spanning tree of a k-connected graph （k ≥ 4）.展开更多
A connected graph G is said to be k-connected if it has more than k vertices and remains connected whenever fewer than k vertices are deleted.In this paper,for a connected graph G with sufficiently large order,we pres...A connected graph G is said to be k-connected if it has more than k vertices and remains connected whenever fewer than k vertices are deleted.In this paper,for a connected graph G with sufficiently large order,we present a tight sufficient condition for G with fixed minimum degree to be k-connected based on the Q-index.Our result can be viewed as a spectral counterpart of the corresponding Dirac-type condition.展开更多
Let σk（G） denote the minimum degree sum of k independent vertices in G and α（G） denote the number of the vertices of a maximum independent set of G. In this paper we prove that if G is a 4-connected graph of ord...Let σk（G） denote the minimum degree sum of k independent vertices in G and α（G） denote the number of the vertices of a maximum independent set of G. In this paper we prove that if G is a 4-connected graph of order n and σ5（G） 〉 n ＋ 3σ（G） ＋ 11, then G is Hamiltonian.展开更多
A. Kaneko and K. Ota proved that for a minimally （n, λ）-connected graph G, if ｜G｜ = p ≥ 3n - 1, then e（G） ≤ nλ（｜G｜ - n）; and if e（G） = nλ（｜G｜ - n）, then G is isomorphic to the graph Kn^λ,p-n whic...A. Kaneko and K. Ota proved that for a minimally （n, λ）-connected graph G, if ｜G｜ = p ≥ 3n - 1, then e（G） ≤ nλ（｜G｜ - n）; and if e（G） = nλ（｜G｜ - n）, then G is isomorphic to the graph Kn^λ,p-n which is obtained from the complete bipartite graph Kn,p-n by replacing each edge with A multiple edges; if 3n - 1 ≥ ｜G}≥ n ＋ 1, then e（G） ≤λ（｜G｜ ＋ n）^2/8. In this paper, we determine all the minimally （n, λ）-connected graphs with order p and the maximum size λ（p＋n）^2/8 for 3n- 1 ≥ p ≥ n＋ 1 for 3n-1≥p≥n＋1.展开更多
基金This paper is supported by the National Natural Science Foundation of China(Nos.11871034,11531011)by the Natural Science Foundation of Jiangsu Province(No.BK20150169).
文摘A path in an edge-colored graph G is called a rainbow path if no two edges of the path are colored the same color.The minimum number of colors required to color the edges of G such that every pair of vertices are connec ted by at least k internally ver tex-disjoint rainbow paths is called the rainbow k-connectivity of the graph G,denoted by rck(G).For the random graph G(n,p),He and Liang got a sharp threshold function for the property rck(G(n,p))≤d.For the random equi-bipartite graph G(n,n,p),Fujita et.al.got a sharp threshold function for the property rck(G(n,n,p))≤3.They also posed the following problem:For d≥2,determine a sharp threshold function for the property rck(G)≤d,where G is another random graph model.This paper is to give a solution to their problem in the general random bipartite graph model G(m,n,p).
基金Supported by NSFC(Nos.12171089,12271235)NSF of Fujian Province(No.2021J02048)。
文摘A graph G possesses Hamiltonian s-properties when G is Hamilton-connected if s=1,Hamiltonian if s=0,and traceable if s=-1.Let S_A(G)=λ_n(G)-λ_1(G)and S_L(G)=μ_n(G)-μ_2(G)be the spread and the Laplacian spread of G,respectively,whereλ_n(G)andλ_1(G)are the largest and smallest eigenvalues of G,andμ_n(G)andμ_2(G)are the largest and second smallest Laplacian eigenvalues of G,respectively.In this paper,we shall present two sufficient conditions involving S_A(G)and S_L(G)for a k-connected graph to possess Hamiltonian s-properties,respectively.We also derive a sufficient condition on the Laplacian eigenratio μ2(G)/μ(G) for a k-connected graph to possess Hamiltonian s-properties.
基金supported by National Natural Science Foundation of China(11071016)Union Foundation of The Science and Technology Department of Guizhou Province,Anshun GovernmentAnshun University(Qiankehe LH Zi[2014]7500)
文摘Let G be a k-connected graph, and T be a subset of V（G）. If G-T is not connected,then T is said to be a cut-set of G. A k-cut-set T of G is a cut-set of G with │T│=k. Let T bea k-cut-set of a k-connected graph G. If G - T can be partitioned into subgraphs G1 and G2such that │G1│≥ 2, │G2│ 〉 2, then we call T a nontrivial k-cut-set of G. Suppose that G is a（k-1）-connected graph without nontrivial （k - 1）-cut-set. Then we call G a quasi k-connectedgraph. In this paper, we prove that for any integer k ≥ 5, if G is a k-connected graph withoutK4-, then every vertex of G is incident with an edge whose contraction yields a quasi k-connectedgraph, and so there are at least │V（G）│/2 edges of G such that the contraction of every member ofthem results in a quasi k-connected graph.
基金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 the Major State Basic Research Development Program of China(973 Program)(Nos.2010CB328202,2010CB328204,and 2012CB315604)the HiTech Research and Development Program of China(863 Program)(Nos.2012AA01Z301,and 2012AA011302)+2 种基金the National Natural Science Foundation of China(No.60702005)the Beijing Nova Program(No.2011065)the Fundamental Research Funds for the Central Universities
文摘This paper proposes k-regular and k-connected(k&k) structure against multifaults in ultra-high capacity optical networks.Theoretical results show that pre-configured k&k structure can reach the lower bound on logical redundancy.The switching time of k&k protection structure is as quickly as ringbased protection in SDH network.It is the optimal protection structure in ultra-high capacity optical networks against multi-faults.We develop the linear programming model for k&k structure and propose a construction method for k&k structure design.Simulations are conducted for spare spectrum resources effi ciency of the pre-confi gured k&k structure under multi-faults on representative COST239 and NSFnet topologies.Numerical results show that the spare spectrum resources efficiency of k&k structure can reach the lower bound on logical redundancy in static networks.And it can largely improve spare spectrum resources effi ciency compared with p-cycles based protection structure without reducing protection effi ciency under dynamic traffi cs.
基金Supported by NSFC(No.12011530064)Natural Science Foundation of Shanghai(No.22ZR1416300)。
文摘Let G be a graph on n vertices whose degree sequence is d_(1)≥…≥d_(n).For a positive integer p,the degree power of G is defined by e_p(G)=∑_(i=1)^(n) d_(i)^(p).In this paper,by majorization,we prove that for a minimally k-connected graph G of order n≥4k,it always holds e_(2)(G)≤kn(n-k)and the extremal graph is K_(k,n-k).Furthermore,we respectively determine the maximum degree powers among all minimally 2(3)-connected graphs and minimally 2-edgeconnected graphs,whose extremal graphs are also characterized.
文摘One of the fundamental properties of an ad hoc network is its connectivity. Maintaining connectivity in wireless networks is extremely difficult due to dynamic changing topology of MANETs. There are several techniques to understand the connectivity level for a given network topology. In this paper, we examine the existing methods and discuss the issues and challenges that are still insurmountable in order to enhance the connectivity properties of wireless multi hop networks.
基金This research has been funded with the support of the project SP2021/45,assigned to VSB-Technical University of Ostrava,the Ministry of Education,Youth and Sports in the Czech Republic.
文摘In Wireless Sensor Network(WSN),coverage and connectivity are the vital challenges in the target-based region.The linear objective is to find the positions to cover the complete target nodes and connectivity between each sensor for data forwarding towards the base station given a grid with target points and a potential sensor placement position.In this paper,a multiobjective problem on target-based WSN(t-WSN)is derived,which minimizes the number of deployed nodes,and maximizes the cost of coverage and sensing range.An Evolutionary-based Non-Dominated Sorting Genetic Algorithm-II(NSGA-II)is incorporated to tackle this multiobjective problem efficiently.Multiobjective problems are intended to solve different objectives of a problem simultaneously.Bio-inspired algorithms address the NP-hard problem most effectively in recent years.In NSGA-II,the Non-Dominated sorting preserves the better solution in different objectives simultaneously using dominance relation.In the diversity maintenance phase,density estimation and crowd comparison are the two components that balance the exploration and exploitation phase of the algorithm.Performance of NSGA-II on this multiobjective problem is evaluated in terms of performance indicators Overall Non-dominated Vector Generation(ONGV)and Spacing(SP).The simulation results show the proposed method performs outperforms the existing algorithms in different aspects of the model.
基金supported by the Innovation Projects of Qinghai Minzu University(No.07M2024008)AFSFQH(No.2022-ZJ-753).
文摘The generalized kt-connectivity K(k)(G)and k-edge-connectivityλ_(k)(G)of a graph G are a natural generalization of traditional connectivity K(G)and edge connectivityλ(G),respectively,which for K(G)=K_(2)(G)andλ(G)=λ_(2)(G).They are important parameters which can often be used to measure the reliability and fault tolerance of interconnection networks.CRNs is a new family of composite networks based on the complete graph,which contain common networks and have the same structural properties as alter-nating group network,and may also include some unknown networks.In this paper,we investigate the generalized 3-connectivity and 3-edge-connectivity of CRNs,and show that K_(3)(G_(l),m)=λ_(3)(G_(l)m)=m-2.
基金Supported by the Science-technology Foundation for Young Scientists of Fujian Province （Grant No. 2007F3070） and National Natural Science Foundation of China （Grant No. 10831001）
文摘An edge e of a k-connected graph G is said to be a removable edge if G e is still kconnected, where G e denotes the graph obtained from G by deleting e to get G - e, and for any end vertex of e with degree k - 1 in G - e, say x, delete x, and then add edges between any pair of non-adjacent vertices in NG-e（x）. The existence of removable edges of k-connected graphs and some properties of 3-connected graphs and 4-connected graphs have been investigated. In the present paper, we investigate some properties of k-connected graphs and study the distribution of removable edges on a cycle in a k-connected graph （k ≥ 4）.
基金Supported by the National Natural Science Foundation of China(No.11171134)the Fujian Province Science Foundation(No.2013J01014,2011J01015,2007F3070)
文摘An edge e of a k-connected graph G is said to be a removable edge if G O e is still k-connected, where G O e denotes the graph obtained from G by the following way： deleting e to get G - e, and for any end vertex of e with degree k - 1 in G - e, say x, deleting x, and then adding edges between any pair of non-adjacent vertices in NG-e （x）. The existence of removable edges of k-connected graphs and some properties of k-connected graphs have been investigated. In the present paper, we investigate the distribution of removable edges on a spanning tree of a k-connected graph （k ≥ 4）.
基金the National Natural Science Foundation of China(Nos.11971311,12161141003,and 12026230)Science and Technology Commission of Shanghai Municipality(No.22JC1403600)+1 种基金Li-Hua Feng and Wei-Jun Liu are partly supported by the National Natural Science Foundation of China(Nos.11871479,12071484)Hunan Provincial Natural Science Foundation(Nos.2020JJ4675,2018JJ2479).
文摘A connected graph G is said to be k-connected if it has more than k vertices and remains connected whenever fewer than k vertices are deleted.In this paper,for a connected graph G with sufficiently large order,we present a tight sufficient condition for G with fixed minimum degree to be k-connected based on the Q-index.Our result can be viewed as a spectral counterpart of the corresponding Dirac-type condition.
基金Supported by NNSF of China (Grant No. 60373012)supported by NSFC (Grant No. 10601044)XJEDU2006S05
文摘Let σk（G） denote the minimum degree sum of k independent vertices in G and α（G） denote the number of the vertices of a maximum independent set of G. In this paper we prove that if G is a 4-connected graph of order n and σ5（G） 〉 n ＋ 3σ（G） ＋ 11, then G is Hamiltonian.
基金This research is supported by the National Natural Science Foundation of China.
文摘A. Kaneko and K. Ota proved that for a minimally （n, λ）-connected graph G, if ｜G｜ = p ≥ 3n - 1, then e（G） ≤ nλ（｜G｜ - n）; and if e（G） = nλ（｜G｜ - n）, then G is isomorphic to the graph Kn^λ,p-n which is obtained from the complete bipartite graph Kn,p-n by replacing each edge with A multiple edges; if 3n - 1 ≥ ｜G}≥ n ＋ 1, then e（G） ≤λ（｜G｜ ＋ n）^2/8. In this paper, we determine all the minimally （n, λ）-connected graphs with order p and the maximum size λ（p＋n）^2/8 for 3n- 1 ≥ p ≥ n＋ 1 for 3n-1≥p≥n＋1.
