简单连通图的k阶幂图的指数集(英文)

The Exponent Set of the kth Power Graphs of Connected Simple Graphs

设Ｇ 是一个ｎ 阶简单连通图，ｋ≥２ 是一个整数．Ｇ 的ｋ 阶幂图记作Ｇｋ ，定义为：Ｖ（ Ｇｋ） ＝ Ｖ（ Ｇ） 且对任意ｕ ，ｖ∈Ｖ（ Ｇｋ） （ ｕ≠ｖ） ，（ ｕ ，ｖ） ∈Ｅ（ Ｇｋ） 当且仅当ｄＧ（ ｕ ，ｖ） ≤ｋ ，则对任意的ｋ≥２ ，Ｇｋ 本原．令Ｅ（ｋ，ｎ） ＝ ｛ γ（ Ｇｋ）｜ Ｇ 是ｎ阶简单连通图｝ ，可以得到Ｅ（ｋ ，ｎ） ＝ｄｋ ｋ＋ １ ≤ｄ ≤ｎ － １ ， 若２ ≤ｋ≤ｎ － ２ ，｛２｝ ， 若ｋ≥ｎ － １ ．

Let G be a connected simple graph of order n and k an integer with k ≥2. The k th power graph of G , denoted by G k , is defined as a graph with V(G k)=V(G) and for any u,v∈V(G k) (u≠v), (u,v)∈E(G k) if and only if d G(u,v)≤k . Then G k is primitive for any k≥2 . Let E(k,n)={γ(G k)|G is a connected simple graph of order n }. In this paper, we obtainE(k,n)=dkk+1≤d≤n-1, if 2≤k≤n-2, {2}, if k≥n-1.