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■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.展开更多
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）.展开更多
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-c...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.展开更多
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.展开更多
基金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■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 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）.
基金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.
基金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.
