检索结果-南通市图书馆

Rainbow Pancyclicity in a Collection of Graphs Under the Dirac-type Condition

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Acta Mathematicae Applicatae Sinica 2024年第2期40卷 269-274页

作者： Lu-yi LI Ping LI Xue-liang LI Center for Combinatorics and LPMC Nankai UniversityTianjin 300071China School of Mathematics and Statistics Shaanxi Normal UniversityXi’an 710062China

Let G={Gi:i∈[n]} be a collection of not necessarily distinct n-vertex graphs with the same vertex set V,where G can be seen as an edge-colored(multi)graph and each Gi is the set of edges with color i.A graph F on V is called rainbow if any two edges of F come from different Gis’.We say that G is rainbow pancyclic if there is a rainbow cycle Cℓof lengthℓin G for each integerℓ2[3,n].In 2020,Joos and Kim proved a rainbow version of Dirac’s theorem:Ifδ(Gi)≥2/n for each i∈[n],then there is a rainbow hamiltonian cycle in *** this paper,under the same condition,we show that G is rainbow pancyclic except that n is even and G consists of n copies of Kn/2,n/*** result supports the famous meta-conjecture posed by Bondy.

关键词： rainbow hamiltonian cycle rainbow pancyclic meta-conjecture

同方期刊数据库

Fault-tolerant hamiltonian cycles and paths embedding into locally exchanged twisted cubes

在线全文

学校读者我要写书评

暂无评论

Frontiers of Computer Science 2021年第3期15卷 59-74页

作者： Weibei FAN Jianxi FAN Zhijie HAN Peng LI Yujie ZHANG Ruchuan WANG College of Computer Nanjing University of Posts and TelecommunicationsNanjing 210023China School of Computer Science and Technology Soochow UniversitySuzhou 215006China Jiangsu High Technology Research Key Laboratory for Wireless Sensor Networks Jiangsu ProvinceNanjing 210003China

The foundation of information society is computer interconnection network,and the key of information exchange is communication *** interconnection networks with simple routing algorithm and high fault-tolerant performance is the premise of realizing various communication algorithms and ***,people can build complex interconnection networks by using very large scale integration(VLSI)*** exchanged twisted cubes,denoted by(s+t+1)-dimensional LeTQ_(s,t) which combines the merits of the exchanged hypercube and the locally twisted *** has been proved that the LeTQ_(s,t) has many excellent properties for interconnection networks,such as fewer edges,lower overhead and smaller *** is an important indicator to measure the performance of interconnection *** mainly study the fault tolerant hamiltonian properties of a faulty locally exchanged twisted cube,LeTQ_(s,t)-(f_(v)+f_(e)),with faulty vertices f_(v) and faulty edges ***,we prove that an LeTQ_(s,t) can tolerate up to s-1 faulty vertices and edges when embedding a hamiltonian cycle,for s≥2,t≥3,and s≤***,we also prove another result that there is a hamiltonian path between any two distinct fault-free vertices in a faulty LeTQ_(s,t) with up to(s-2)faulty vertices and *** is,we show that LeTQ_(s,t) is(s-1)-hamiltonian and(s-2)-*** results are proved to be optimal in this paper with at most(s-1)-fault-tolerant Hamiltonicity and(s-2)fault-tolerant hamiltonian connectivity of LeTQ_(s,t).

关键词： interconnection network fault-tolerant LeTQ_(s,t) hamiltonian cycle hamiltonian path

Matchings extend to hamiltonian cycles in hyper cubes with faulty edges

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Frontiers of Mathematics in China 2019年第6期14卷 1117-1132页

作者： Xie-Bin CHEN College of Mathematics and Statistics Minnan Normal UniversityZhangzhou 363000China

We consider the problem of existence of a hamiltonian cycle containing a matching and avoiding some edges in an n-cubc Qn,and obtain the following *** n≥3,MСE(Qn),and FСE(Qn)\M with 1≤|F|≤2n-4-|M|.If M is a matching and every vertex is incident with at least two edges in the graph Qn-F,then all edges of M lie on a hamiltonian cycle in ***,if|M|=1 or|M|==2,then the upper bound of number of faulty edges tolerated is *** results generalize the well-known result for |M|=1.

关键词： Hypercube hamiltonian cycle fault tolerance matching interconnection network

Fault-free hamiltonian cycles passing through a prescribed linear forest in 3-ary n-cube with faulty edges

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Frontiers of Mathematics in China 2014年第1期9卷 17-30页

作者： Xie-Bin CHEN College of Mathematics and Statistics Minnan Normal University Zhangzhou 363000 China

The k-ary n-cube Qkn （n ≥2 and k ≥3） is one of the most popular interconnection networks. In this paper, we consider the problem of a fault- free hamiltonian cycle passing through a prescribed linear forest （i.e., pairwise vertex-disjoint paths） in the 3-ary n-cube Qn^3 with faulty edges. The following result is obtained. Let E0 （≠θ） be a linear forest and F （≠θ） be a set of faulty edges in Q3 such that E0∩ F = 0 and ｜E0｜＋｜F｜ ≤ 2n - 2. Then all edges of E0 lie on a hamiltonian cycle in Qn^3- F, and the upper bound 2n - 2 is sharp.

关键词： hamiltonian cycle fault-tolerance 3-ary n-cube linear forest interconnection network

Four Forbidden Subgraph Pairs for Hamiltonicity of 3-connected Graphs

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Acta Mathematicae Applicatae Sinica 2016年第2期32卷 469-476页

作者： Hou-yuan LIN Zhi-quan HU School of Mathematics and Quantitative Economics Shandong University of Finance and Economics Faculty of Mathematics and Statistics Central China Normal University

For non-negative integers i,j and k, we denote the generalized net as Ni,j,k, which is a triangle with disjoint paths of length i, j and k, attached to distinct vertices of the triangle. In this paper, we prove that e... 详细信息

关键词： hamiltonian cycle forbidden subgraphs claw-free graphs closure

Decomposition of K2n into n-1 hamiltonian cycles and a perfect matching Mi

在线全文

学校读者我要写书评

暂无评论

Decomposition of K2n into n-1 Hamiltonian Cycles and a perfe...

A Generalization of Implicit Ore-condition for Hamiltonicity of k-connected Graphs

第24届中国控制与决策会议

作者： Zhaodi Xu 1 , Xiaoyi Li 1 , Wanxi Chou 2 1. School of Mathematics and Systems Science, Shenyang Normal University, Shenyang, 110034, China. 2 School of Civil Engineering and Architecture, Anhui University of Science and Technology, Huainan Anhui 232001. China.

Theorem on 2-factorization of complete graph K 2n of even order is proved. Foundamental concepts of 1-factorization and 2-factorization of complete graphs K 2n are described. Construct the edge matrix of the complete graph K 2n edge coloring has been followed Thus the rectangular matrix has been composed by 1-factor of 2n-1 . Determine the collocation programming which is let 2n-1 1-factor combined with n-1 2-factor and 1 1-factor and generated cycles for each 2-factor , In accordance with the different Programming, The process which let E（G） divide into n-1 frontier set of hamiltonian cycles and 1 1-factor .The entire procedure of 2-factorization of complete graphs K 10 K 12 and K 14 is presented.

关键词： complete graph prefect matching hamiltonian cycle factorization even order

来源： cnki会议评论

在线全文

cnki会议

学校读者我要写书评

暂无评论

Acta Mathematicae Applicatae Sinica 2020年第3期36卷 620-626页

作者： Jun-qing CAI Lin WANG School of Management Qufu Normal UniversityRizhao 276826China

In 2005,Flandrin et *** that if G is a k-connected graph of order n and V(G)=X1∪X2∪···∪Xk such that d(x)+d(y)≥n for each pair of nonadjacent vertices x,y∈Xi and each i with i=1,2,···,k,then G is *** order to get more sufficient conditions for hamiltonicity of graphs,Zhu,Li and Deng proposed the definitions of two kinds of implicit degree of a vertex v,denoted by id1(v)and id2(v),*** this paper,we are going to prove that if G is a k-connected graph of order n and V(G)=X1∪X2∪···∪Xk such that id2(x)+id2(y)≥n for each pair of nonadjacent vertices x,y∈Xi and each i with i=1,2,···,k,then G is hamiltonian.

关键词： implicit degree hamiltonian cycle cyclability

The embedding of rings and meshes into RP(k) networks

在线全文

学校读者我要写书评

暂无评论

Science in China(Series F) 2004年第5期47卷 669-680页

作者： LIUFang'ai LIUZhiyong ZHANGYongsheng TheSchoolofInformationManagement ShandongNormalUniversityJinan250014China TheNationalNaturalScienceFoundationofChina Beijing100085China

This paper first investigates the topological properties of RP(k) networks. Then focusing on the embedding of rings and 2-D meshes into the RP(k) network, it is proved that the RP(k) network is a hamiltonian graph and the ring with 10*k nodes can be embedded into the RP(k) network with load, expansion, dilation and congestion all equal to 1. If there exists a faulty node on each slice in the RP(k) network, throwing off the faulty nodes, the RP-1(k) network is obtained. It is also proved that there exists a Hamiltonain cycle in the RP-1(k) network. So the ring with 9*k nodes can be embedded into the RP-1(k) network. After that, we discuss the embedding of a 2-D mesh, M 1(a, b), into the RP(k) network. By defining the sequence-column-order mapping, the snake-like-column-order mapping and the shortest path mapping, we obtain two ways of embedding a 2-D mesh into the RP(k) network. The performances of the embedding are as follows. In the snake-like-column-order mapping, the dilations are 1, 2, 3, 3 and 2 and the congestion are 1, 3, 4, 5 and 3 respectively when a is equal to 1, 2, 3, 4 and 5. In the sequence-column-order mapping, the dilation is equal to 3 and the congestion is equal to 6 when a is between 6 and 9. The dilation is equal to ⌌a/10⌍+2 and the congestion is equal to max{ ⌌a/10⌍+1, 6} when a>10. As a special case, the four parameters are also equal to 1 when a is equal to 10.

关键词： interconnection network RP(k) Petersen graph network embedding hamiltonian cycle dilation congestion.

Two-Level Genetic Algorithm for Clustered Traveling Salesman Problem with Application in Large-Scale TSPs

在线全文

学校读者我要写书评

暂无评论

Tsinghua Science and Technology 2007年第4期12卷 459-465页

作者：丁超成晔何苗 Department of Industrial Engineering Tsinghua University

Let G = （V, E） be a complete undirected graph with vertex set V, edge set E, and edge weights I（e） satisfying the triangle inequality. The vertex set V is partitioned into clusters V1, V2 ,…, Vk. The clustered traveling salesman problem （CTSP） seeks to compute the shortest hamiltonian tour that visits all the vertices, in which the vertices of each cluster are visited consecutively. A two-level genetic algorithm （TLGA） was developed for the problem, which favors neither intra-cluster paths nor inter-cluster paths, thus realized integrated evolutionary optimization for both levels of the CTSP. Results show that the algorithm is more effective than known algorithms. A large-scale traveling salesman problem （TSP） can be converted into a CTSP by clustering so that it can then be solved by the algorithm. Test results demonstrate that the clustering TLGA for large TSPs is more effective and efficient than the classical genetic algorithm.

关键词： clustered traveling salesman problem (CTSP) traveling salesman problem (TSP) hamiltonian cycle genetic algorithm integrated evolutionary optimization