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.展开更多
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）.展开更多
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 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).展开更多
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.展开更多
基金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 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）.
文摘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.
基金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 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.
