关于图中给定端点的 Hamilton-路及 D-路

The Hamilton path and Dominating path with Given Endvertices in a Graph

设Ｇ是有限无向简单图．｛ａ，ｂ｝Ｖ（Ｇ），Ｎ［ａ］＝Ｎ（ａ）∪｛ａ｝．令Ｊ（ａ，ｂ）＝｛ｕ｜ｕ∈Ｎ（ａ）∩Ｎ（ｂ）且Ｎ（ｕ）Ｎ［ａ］∪Ｎ［ｂ］｝．Ｇ称为Ｇ的部分平方图：Ｖ（Ｇ）＝Ｖ（Ｇ），Ｅ（Ｇ）＝Ｅ（Ｇ）∪｛ａｂ｜ａｂＥ（Ｇ），Ｊ（ａ，ｂ）≠｝．设Ｇ是（ｋ＋１）连通图（ｋ≥２），｛ｕ１，ｕ２｝Ｖ（Ｇ）．本文主要结论：（ａ）设Ｇｗ是Ｇ中添加新顶点ｗ及新边ｗｕ１，ｗｕ２所得的图．若对任意Ｙ∈Ｉｋ＋１（Ｇｗ），且ＹＶ（Ｇ），在Ｇ中，有ｋ＋１ｉ＝１ａｉｓｉ（Ｙ）＞ｎ（Ｙ），则Ｇ有Ｈａｍｉｌｔｏｎ（ｕ１，ｕ２）路．（ｂ）设Ｇｗ１ｗ２是由Ｇ添加新顶点ｗ１，ｗ２及新边ｕ１ｗ１，ｗ１ｗ２，ｗ２ｕ２所得的图．若对于任意Ｙ∈Ｉｋ＋１（Ｇｗ１，ｗ２），且ＹＶ（Ｇ），在Ｇ中，有ｋ＋１ｉ＝１ａｉｓｉ（Ｙ）＋ｓｋ＋１（Ｙ）＞ｎ（Ｙ）＋ｋ＋１，则Ｇ中最长的（ｕ１，ｕ２）路是Ｄ路．

Let G be an undirected finite simple graph. {a,b}V(G). Denote N=N(a)∪{a} and J(a,b)={uu∈N(a)∩N(b),N(u)N∪N}. A graph G is called the partially squared graph of G if V(G)=V(G ) and E(G )=E(G)∪{ababE(G),J(a,b)≠ }. Let I t(G)={YY be an independent set with Y=t}. In this paper,Let G be (k+1) connected graph with k≥2,{u 1,u 2}V(G), and non negative rational sequence (a 1,…,a k+1 ) be an LTW sequence . The following results are obtained.(a) Let G w be the graph obtained from G by adding a new vertex w and new edges wu 1,wu 2. If k+1i=1a isi(Y)>n(Y) in G for any Y∈I k+1 (G w) and YV(G), then G contains a hamilton (u 1,u 2) path . (b)Let G w 1w 2 be the graph obtained from G by adding two new vertices w 1,w 2 and three new edges u 1w 1,w 1w 2,w 2u 2. If k+1i=1a is i(Y)+s k+1 (Y)>n(Y)+k+1 in G for any Y∈I k+1 (G w 1w 2 ) and Y V(G) , then the longest (u 1,u 2) path in G is a dominating path.