运筹学学报
運籌學學報
운주학학보
OR TRANSACTIONS
2008年
4期
19-24
,共6页
运筹学%线图%无爪图%闭迹%哈密顿圈
運籌學%線圖%無爪圖%閉跡%哈密頓圈
운주학%선도%무조도%폐적%합밀돈권
Operations research%line graphs%claw-free graphs%closed trail%Hamilton cycle
不包含2K2的图是指不包含一对独立边作为导出子图的图.Kriesell证明了所有4连通的无爪图的线图是哈密顿连通的.本文证明了如果图G不包含2K2并且不同构与K2,P3和双星图,那么线图L(G)是哈密顿图,进一步应用由Ryj á(c)ek引入的闭包的概念,给出了直径不超过2的2连通无爪图是哈密顿图这个定理的新的证明方法.
不包含2K2的圖是指不包含一對獨立邊作為導齣子圖的圖.Kriesell證明瞭所有4連通的無爪圖的線圖是哈密頓連通的.本文證明瞭如果圖G不包含2K2併且不同構與K2,P3和雙星圖,那麽線圖L(G)是哈密頓圖,進一步應用由Ryj á(c)ek引入的閉包的概唸,給齣瞭直徑不超過2的2連通無爪圖是哈密頓圖這箇定理的新的證明方法.
불포함2K2적도시지불포함일대독립변작위도출자도적도.Kriesell증명료소유4련통적무조도적선도시합밀돈련통적.본문증명료여과도G불포함2K2병차불동구여K2,P3화쌍성도,나요선도L(G)시합밀돈도,진일보응용유Ryj á(c)ek인입적폐포적개념,급출료직경불초과2적2련통무조도시합밀돈도저개정리적신적증명방법.
A graph iS called 2K2-free if it does not contain an independent pair of edges as an induced subgraph.Kriesell proved that all 4-connected line graphs of claw.free graph axe Hamiltonian-connected.Motivated from this,in this note,we show that if G is 2K2-free and is not isomorphic to K2,P3 or a double star,then the line graph L(G)isHamiltonian.Moreover,by applying the closure concept of claw-free graphs introduced byby Ainouche et al.,which says that every 2-connected claw-free graph of diameter at most 2 is Hamiltonian.
