论文部分内容阅读
为了研究图直积运算的消去律问题，即: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哈密尔顿性的证明。