论文部分内容阅读
为了研究图直积运算的消去律问题,即:G×K≌H×K当且仅当G≌H.Hammack和Liversay引入了一种称为内幂的新的图运算:一个图G的k次内幂G(k)的顶点集为V(G(k))={(x0x1…xk-1)∶xi∈V(G),i=0,1,…,k-1};边集为E(G(k))={(x0x1…xk-1)(y0y1…yk-1)∶xiyi±1∈E(G),i=0,1,…,k-1}。 Wang和Yan在文[3]中提出了关于图内幂的如下猜想:猜想[3].设G是一个具有哈密尔顿圈1234…n且无重边的图。则G(2)是哈密尔顿图当且仅当n是奇数或G包含两条弦uv和st,满足:u,v为偶数且s,t为奇数。 本文通过对G(2)结构的刻画证明该猜想是成立的。此外,对一般的正整数k,确定了G(k)的边数,简化了文[3]中关于C(k)n哈密尔顿性的证明。