边赋权简单图最长圈问题研究  

Research on the Longest Cycle of Edge Weighted Simple Graphs

作　　者：张智微 李鹏 ZHANG Zhiwei;LI Peng(College of science, Chongqing University of Technology, Chongqing 400054, China)

机构地区：[1]重庆理工大学理学院,重庆400054

出　　处：《重庆理工大学学报（自然科学）》2021年第9期220-226,共7页Journal of Chongqing University of Technology：Natural Science

基　　金：国家自然科学基金项目(11701059)。

摘　　要：最长圈问题是图论中重要的研究课题,它起源于汉密尔顿圈问题。边赋权图是边上赋正值的图。边赋权图的最长圈,是指所有边权值之和最大的圈。图论中有个著名猜想,即2连通弦图所有最长圈都经过同1个顶点。该猜想与边赋权区间图的最长圈问题紧密相关。研究了边赋权简单图(即只有2个极大团的图)的最长圈问题,并证明了该图上所有最长圈经过同1个顶点。The longest cycle problem is an important research topic in graph theory,which originated from Hamilton cycle problem.Edge weighted graphs are graphs with positive values on the edges.The longest cycle of edge weighted graph is the cycle with the largest sum of all edge weights.There is a famous conjecture in graph theory that all the longest cycles of a chord graph pass through the same vertex.This conjecture is closely related to the longest cycle problem of edge weighted interval graphs.This paper studies the longest cycle problem of a simple graph with edge weighting(i.e.a graph with only 2 maximal cliques),and proves that all the longest cycles in the graph pass through the same vertex.

关 键 词：最长圈问题 边赋权图 简单图 

分 类 号：O157.5[理学—数学]