安新慧, 黄琼湘, 刘晓平. 关于中间图补图的一个定理的简单证明(英文)[J]. Journal of Xinjiang University (Natural Science Edition in Chinese and English), 2008, 110(2): 127-130.DOI：
关于中间图补图的一个定理的简单证明(英文)
摘要
对于图G
定义它的中间图M(G)的顶点集为V(G)∪ E(G)
顶点集中的两点x和y在M(G)中相邻当且仅当{x
y}∪ E(G)≠
并且x和y在G中相邻或者关联.在这篇文章中简化了下面这个最近已经得到的定理的证明
即一个图G的中间图M(G)的补图是哈密顿的当且仅当G不是星图
并且G不同构于{K1
2K1
K2
K2∪ K1
K3
K3∪ K1}中的任意一个图.
Abstract
For a graph G
the middle graph M(G) of G is the graph with vertex set V(G)∪E(G) in which the vertices x and y are joined by an edge if {x
y}∪E(G)≠ф
and x and y are adjacent or incident in G.In this note
we provide a simple proof for a theorem
recently obtained by An and Wu
which says that the complement of middle graph M(G) of a graph G is hamiltonian if and only if G is not a star and is not isomorphic to any graph in {K1
2K1
K2
K2∪K1
K3
K3∪K1}.
关键词
Keywords
references
An X,Wu B.Hamiltonicity of complements of middle graphs[J].Discrete Math,2007,307: 1178-1184.
Bondy J A,Murty U S R.Graph Theory with Applications[M].American Elsevier,New York: Macmillan, London,1976.
Chartrand G,Hevia H,Jarrett E B,Schultz M.Subgraph Distances in Graphs Defined by Edge Transfers[J]. Discrete Math,1997,170: 63-79.
Hamada T,Yoshimura I.Traversability and connectivity of the middle graph of a graph[J].Discrete Math,1976, 14: 247-255.
Harary F,Nash-Williams C St J A.On eulerian and hamiltonian graphs and line graphs[J].Canad Math Bull,1965, 8:701-709.
京公网安备11010802024621