利用图的顶点和边的标号函数来研究图的理论是在1966年由Stewart引入的, 多年来国内外许多研究者致力于这方面的研究, 且获得了一系列的研究成果.图的平衡指数集是将图的顶点和边通过映射函数与数集对应, 进而研究各类图的特征和内在特性, 完成图的指数集的公式推导和证明, 平衡指数集的理论可以应用到信息工程, 通讯网络, 编码理论, 计算机科学, 经济管理, 医学等方面. 1995年, Sin-Min Lee在文献[10]中定义了边-平衡图和强边-平衡图, 研究了一些图的边-平衡性和强边-平衡性, 并提出了两个猜想: (1) 除了 $Sn(n$是奇数), 所有的树都是边-平衡的; (2) 除了 $K_2$, 所有连通的正则图都是边-平衡的.

2002年, Chen等在文献[5]中扩充了边-平衡多重图的概念, 证明了文献[10]中的猜想是正确的, 并给出一个图是边-平衡的不是NP-难问题. 2008年, Alexander、Harris等在文献[2, 4, 6]中研究了图的点-平衡指数集和友好指数集, Suh-Ryung在文献[7]中运用构造法研究了新的边-平衡图族. 2010年文献[8]中Chopra等研究了轮图的边-平衡指数集, 2011年文献[9]中Sin-Min Lee, Chou, Galiardi, Kong, 等人研究了星圈交图的边-平衡指数集. 2009年以来, 郑玉歌及其学生首次提出了无限链图和无限嵌套图的研究, 在文献[10]中研究了Ⅰ型 $K_4$ $-e$链的边-平衡指数集, 确定了其完备指数集和完美指数集, 在文献[11, 13]中完全解决了 $C_n\times P_m$ $(n\geq 3, m\geq2)$的边-平衡指数集问题.本文在无限路等圈嵌套图的基础上, 提出带齿套圈子图的概念, 通过对带齿套圈子图和基础图的研究, 运用套圈计算的方法给出无限路幂圈嵌套图 $C_{3^m}\times P_{m_3}(m\geq3)$最大的边-平衡指数的计算公式, 最后完全解决此类图的边-平衡指数集问题.

设 $f$是图 $G$的边集 $E(G)$上的一个 $0, 1$标号, 即 $\forall e\in E(G)$, 定义 $f\{e\}=0$或 $1$, 标号 $0$或 $1$的边集分别记为 $E(0), E(1)$, 用 $e(0), e(1)$分别来表示此二集合的基数.由 $f$诱导出一个顶点标号 $f^+:V(G)\rightarrow\{0, 1\}$是这样定义的:

$ f^+(x)=\left\{ \begin{array}{ll} 0,&e_x(0)>e_x(1);\\ 1,&e_x(1)>e_x(0);\\ \mbox{不定义},&e_x(0)=e_x(1) \end{array} \right. $

( $e_x(0), e_x(1)$表示与 $x$关联的边中标号为 $0$或 $1$的边集合的基数).

图 $G$中标号为 $0$或 $1$的顶点集分别记为 $V(0), V(1)$, 它们的基数分别记为 $v(0), v(1)$.

定义2.1^[1]  设 $f$是图 $G$的边集 $E(G)$上的一个 $0, 1$标号, 如果 $\arrowvert e_f(0)-e_f(1)\arrowvert$ $\leq 1 $, 那么就称 $f$为图 $G$的边-友好标号.

定义2.2^[1]  如果图 $G$存在边-友好标号 $f$, 则称集合 $\{\arrowvert v_f (0)-v_f(1)\arrowvert\:$标号 $f$是友好的 $\}$为图 $G$的边-平衡指数集, 记为 $EBI(G)$.

定义2.3  幂圈套图表示 $m$个圈的图, 其中最内圈有 $n$个顶点, 且从内到外圈上顶点数以幂次方(即 $n^1, n^2, n^3, \cdots, n^{m-1}, n^m$)依次增加的.记为 $C_{n^m}$, 其中

$ \begin{eqnarray*} V(C_{n^m})& =& \{(i)_j\arrowvert 1\le i\le m, 1\le j\le k^i, 2\le k\le n\};\\ E(C_{n^m})& =& \{((i)_j(i)_{j+1})\arrowvert 1\le i\le m, 1\le j\le k^i-1, 2\le k\le n\}\\ & \bigcup& \{((i)_{k^m}(i)_1)\arrowvert1\le i\le m, 2\le k\le n\}. \end{eqnarray*} $

定义2.4  无限路形图表示 $n^m$条包含 $m$个顶点的路, 且路中除路的终点外其他点处均有 $n$个分叉的.记为 $P_{m_n}$, 其中

$ \begin{eqnarray*} V(P_{m_n})& =& \{(i)_j\arrowvert 1\le i\le m, 1\le j\le k^i, 2\le k\le n\};\\ E(P_{m_n})& =& \{((i)_j(i+1)_{kj-r})\arrowvert 1\le i\le m, 1\le j\le k^i, 2\le k\le n, 0\le r \le k-1\}. \end{eqnarray*} $

定义2.5  无限路幂圈嵌套图表示由幂圈套图 $C_{n^m}$与无限路形图 $P_{m_n}$嵌套构成的.记为 $C_{n^m}\times P_{m_n}$, 其中

$ \begin{eqnarray*} V(C_{n^m}\times P_{m_n})& =& V(C_{n^m})=V(P_{m_n}), \\ E(C_{n^m}\times P_{m_n})& =& E(C_{n^m})\bigcup E(P_{m_n}). \end{eqnarray*} $

定义2.6  若与点 $x$关联的 $n$条边, 满足 $e_x(1)-e_x(0)=1$或0, 则称 $x$为饱和 $1$-点, 否则称为不饱和 $1$-点.与 $x$关联的 $n$条边, 满足 $e_x(0)=n$则称 $x$为饱和0 -点, 否则称为不饱和0 -点.

方便起见, 我们对图进行以下标号:

最里圈上的点顺时针依次记为 $(1)_1, (1)_2, \cdots, (1)_{n-1}, (1)_n$.类似的, 从里向外依次将圈上的点按顺时针用 $(m)_1, (m)_2, \cdots, (m)_{n^m-1}, (m)_{n^m}$标号, 其中符号 $(j)_i$表示第 $j$圈上的第 $i$个点.

以 $(1)_1$作为起点的路有如下:

$ \begin{eqnarray*}&& (1)_1\to (2)_1\to(3)_1\to \cdots \to(m-1)_1\to(m)_1;\\ && (1)_1\to (2)_1\to(3)_1\to \cdots \to(m-1)_1\to(m)_2;\\ && \cdots\\ && (1)_1\to (2)_1\to(3)_1\to \cdots \to(m-1)_1\to(m)_m;\\ && (1)_1\to (2)_1\to(3)_1\to \cdots \to(m-1)_2\to(m)_{m+1};\\ && \cdots\\ && (1)_1\to (2)_{n^1}\to(3)_{n^2}\to \cdots \to(m-1)_{n^{m-2}}\to(m)_{n^{m-1}-1};\\ && (1)_1\to (2)_{n^1}\to(3)_{n^2}\to \cdots \to(m-1)_{n^{m-2}}\to(m)_{n^{m-1}}.\end{eqnarray*} $

类似的以 $(1)_n$作为起点的路如下:

$ \begin{eqnarray*}&& (1)_n\to (2)_{n^2-n+1}\to(3)_{n^3-n^2+1}\to \cdots \to(m-1)_{n^{m-1}-n^{m-2}+1}\to(m)_{n^m-n^{m-1}+1};\\ && (1)_n\to (2)_{n^2-n+1}\to(3)_{n^3-n^2+1}\to \cdots \to(m-1)_{n^{m-1}-n^{m-2}+1}\to(m)_{n^m-n^{m-1}+2};\\ && \cdots\\ && (1)_n\to (2)_{n^2-n+1}\to(3)_{n^3-n^2+1}\to \cdots \to(m-1)_{n^{m-1}-n^{m-2}+1}\to(m)_{n^m-n^{m-1}+n};\\ && (1)_n\to (2)_{n^2-n+1}\to(3)_{n^3-n^2+1}\to \cdots \to(m-1)_{n^{m-1}-n^{m-2}+1}\to(m)_{n^m-n^{m-1}+n+1};\\ && \cdots\\ && (1)_n\to (2)_{n^2}\to(3)_{n^3}\to \cdots \to(m-1)_{n^{m-1}}\to(m)_{n^m-1};\\ && (1)_n\to (2)_{n^2}\to(3)_{n^3}\to \cdots \to(m-1)_{n^{m-1}}\to(m)_{n^m}.\end{eqnarray*} $

这就是图 $C_{n^m}\times P_{m_n}$中的 $n^m$条路.

注1  图 $G$中最大的边-平衡指数用max $\{EBI(G)\}$来表示.

注2  在不混淆的情况下, 我们把图中标号为 $0$（或 $1$）的边记为 $0$-边（或 $1$-边）, $0$-点（或 $1$-点）表示标号为 $0$（或 $1$）的顶点.

注3   $(2k-1)_r(2k)_s\leftrightarrow(2k)_s(2k)_{s+1}$表示边 $(2k-1)_r(2k)_s$由0-边变为1-边, 同时边 $(2k)_s(2k)_{s+1}$由1-边变为0-边.

注4  在构造边平衡指数集的标号图时, 所做的每一步变换都是在上一步的基础上完成的.

注5  文中所有涉及的参数无特殊说明均为自然数.

本文在无限路幂圈嵌套图的基础上引入带齿套圈子图的概念, 通过对带齿套圈子图和基础图的研究, 运用套圈计算的方法给出无限路幂圈嵌套图 $C_{3^m}\times P_{m_3}(m\ge 3)$最大的边-平衡指数的计算公式, 以及平衡指数集对应标号图形的构造.对于图进行边-友好标号, 我们将 $m$分为4类: $m\equiv 3($mod4 $)$; $m\equiv0($mod4 $)$, $m\equiv1($mod4 $)$; $m\equiv2($mod $4)$, 分别来讨论其边-平衡指数集.

例3.1  下面给出了几个 $C_{3^m}\times P_{m_3}$图.

在幂圈嵌套图的定义下, 为了更简便的给出图的标号图形, 根据幂圈嵌套图的递推性, 给出带齿套圈子图的定义.

定义3.1  在无限路幂圈嵌套图中, 以第 $k(t-1)+i$圈上的点作为起点, 第 $kt+i$圈上的点为终点的路形图所经过的点的导出子图, 记作 $T^{'}_{t}$, 在其基础上去掉第 $k(t-1)+i$圈上的边得到的图, 记作 $T_t(t=1, 2, \cdots, \frac {m-i}{k})$, 称为第 $t$个带齿 $k$套圈子图.特别的 $k$由 $m$的分类决定, 在图 $C_{3^m}\times P_{m_3}(m\ge 3)$中所指的套圈子图均为带齿4套圈子图.

引理3.1  在幂圈嵌套图 $C_{3^m}\times P_{m_3}(m\ge 3)$中, 对于给定的带齿套圈子图 $T_t~ (t=1, 2, \cdots, \frac {m-i}{4})~(i=3, 4, 5, 6)$, 若路形图的起点记作第 $\partial$圈上的点, 从内到外依次经过的圈记为第 $\partial+1$圈, 第 $\partial+2$圈, 第 $\partial+3$圈, 第 $\partial+4$圈, 则该带齿套圈子图的最大边-平衡指数为 $3^{\partial+4}-3^\partial$.

证  首先, 构造最大边-平衡指数对应的标号图.

在路形图中, 将路径

$ \begin{eqnarray*}&& (\partial)_a(\partial+1)_b(\partial+2)_c(\partial+3)_d(\partial+4)_e~ (1\leq a\leq 3^\partial ;\\ && b=2+3r, \ 1\leq b \leq 3^{\partial+1} ;\\ && c=4+r+9s, r=0, 1, 2, \ 1 \leq c \leq 3^{\partial+2};\\ && d=10+r+27s, \ r=0, 1, \cdots, 8, \ 1\leq d\leq 3^{\partial+3};\\ && e=28+r+81s, \ r=0, 1, \cdots, 26, \ 1\leq e \leq 3^{\partial+4})\end{eqnarray*} $

中的边均标为0-边, 同时路径

$ \begin{eqnarray*}&& (\partial+1)_b(\partial+2)_c(\partial+3)_d(\partial+4)_e ( b=1+3r, \ 1\leq b \leq 3^{\partial+1} ;\\ && c=3+9s, \ 1 \leq c \leq 3^{\partial+2};\ d=7+r+27s, \ r=0, 1, 2, \ 1\leq d\leq 3^{\partial+3};\\ && e=19+r+81s, \ r=0, 1, \cdots, 8, \ 1\leq e \leq 3^{\partial+4})\end{eqnarray*} $

和

$ \begin{eqnarray*}&& (\partial+1)_b(\partial+2)_c(\partial+3)_d(\partial+4)_e ( b=3+3r+9s, r=0, 1, \ 1\leq b \leq 3^{\partial+1} ;\\ && c=7+9r+27s, r=0, 1, 1 \leq c \leq 3^{\partial+2};\\ && d=19+r+27s+81t, \ r=0, 1, 2, \ s=0, 1, \ 1\leq d\leq 3^{\partial+3};\\ && e=55+r+81s+127t, \ r=0, 1, \cdots, 8, \ s=0, 1, \ 1\leq e \leq 3^{\partial+4})\end{eqnarray*} $

以及

$ \begin{eqnarray*}&& (\partial+2)_c(\partial+3)_d(\partial+4)_e ( c=25+27s, \ 1 \leq c \leq 3^{\partial+2};\\&& d=73+81s, \ 1\leq d\leq 3^{\partial+3};\\ && e=217+r+243s, \ r=0, 1, 2, 1\leq e \leq 3^{\partial+4})\end{eqnarray*} $

上的边均标号为0.另外将路中边

$ (\partial+1)_b(\partial+2)_c(b=9+9r, \ 1\leq b \leq 3^{\partial+1};\ c=26+27r, \ 1\leq c\leq 3^{\partial+2}) $

标号为0, 其余边均标号为1.

在幂圈套图中, 将第 $\partial+1$圈中弧

$ (\partial+1)_i(\partial+1)_{i+1}(\partial+1)_{i+2}(i=1+3r, \ 1 \leq i \leq 3^{\partial+1}) $

边标号为0;将第 $\partial+2$圈上除边$ (\partial+2)_i(\partial+2)_{i+1}(i=25+27r, \ 1 \leq i \leq 3^{\partial+2})$外均标号为0;第 $\partial+3$圈上的边均为0-边; 第 $\partial+4$圈上边

$ (\partial+4)_i(\partial+4)_{i+1}(i=1+2r+63s+81u, \ r=0, 1, \cdots, 8, \ s=0, 1; $

或

$ i=220+2t+243u, \ t=0, 1, 2, \ 1 \leq i \leq 3^{\partial+4}) $

标号为0, 其它边则都标号为1.

在带齿套圈子图 $T_t(t=1, 2, \cdots, \frac {m-i}{4})(i=3, 4, 5, 6)$中, 共有 $80\times3^{\alpha+1}$条边, 其中0-边有 $40\times3^{\partial+1}$条.由边-友好标号的定义, 即 $|e_f(0)-e_f(1)|\leq1$, 通过计算, 在上述构造图中的边为友好标号.在构造的标号图中, 第 $\partial+1$圈上顶点 $(\partial+1)_i(i=2+3t, 1\leq i \leq 3^{\partial+1})$和第 $\partial+2$圈上顶点

$ \begin{eqnarray*}&& (\partial+2)_i(i=3+s+9t, s=0, 1, 2, 3, 4, \ 1\leq i \leq 3^{\partial+2}), \\ && (\partial+2)_i(i=21+s+27t, s=0, 1, 2, 3, \ 1\leq i \leq 3^{\partial+2})\end{eqnarray*} $

以及第 $\partial+3$圈上顶点

$ \begin{eqnarray*}&& (\partial+3)_{3i-r}(i=3+s+9t, \ s=0, 1, 2, 3, 4, \ 1\leq i \leq 3^{\partial+3};\ r=0, 1, 2), \\ && (\partial+3)_{3i-r}(i=21+s+27t, \ s=0, 1, 2, 3, \ 1\leq i \leq 3^{\partial+3};\ r=0, 1, 2), \\ && (\partial+3)_i(i=73+81t, \ 1\leq i \leq 3^{\partial+3})\end{eqnarray*} $

均为0-点, 其它顶点都为1-点, 可知0-点有 $20\times3^\partial$个.

又因为该带齿套圈子图中共有 $40\times3^{\partial+1}$个点, 且图中每个顶点都在顶点标号 $f^+$下定义, 这样就得到 $ |v(0)-v(1)|=3^{\partial+4}-3^\partial. $

可以证明 $3^{\partial+4}-3^\partial$为该带齿套圈子图的最大边-平衡指数.

因为在上述标号的带齿套圈子图中, 第 $\partial$圈和第 $\partial+4$圈上点均为三度饱和1 -点, 在带齿套圈子图嵌套过程中不会改变其点的标号特征.其他圈上的点也均为6度饱和点, 又由于任意一个1 -点或不定义变为0 -点, 只需增加一条0 -边; 同时如果想0 -点变为1 -点或不定义点, 至少要去掉3条0 -边.而在上述构造图中的任意一条0 -边和1 -边互换, 0 -点的个数不会减少, 而1 -点的个数必要减少, 此时 $|v(0)-v(1)|$的值必减小, 因此 $3^{\partial+4}-3^\partial$为该图的最大边-平衡指数, 即

$ \begin{eqnarray*} \max\{EBI(T_t(t=1, 2, \cdots, \frac {m-i}{4})(i=3, 4, 5, 6))\} = 3^{\partial+4}-3^\partial. \end{eqnarray*} $

引理3.2  在幂圈嵌套图 $C_{3^3}\times P_{3_3}$中, 最大的边-平衡指数为 $3^3$即27.

证  在这里, 我们首先给出该图的最大边-平衡指数对应的标号图.

令与点 $(1)_2, (2)_a(a=3, 4, 5, 6, 7)$相关联的边为0 -边, 同时第2圈上的边和边 $(3)_1(3)_2$, $(3)_3(3)_4$, $(3)_5(3)_6, (3)_{22}(3)_{23}, (3)_{24}, (3)_{25}, (3)_{26}, (3)_{27}$标号为0, 其它边则都标号为1.经计算上述构造图满足友好标号, 在图中共有6个0-点, 其余均为1-点, 而图中共有39个点, 这样就得到 $ |v(0)-v(1)|=27. $

在上述构造图中, 第一圈上的点均为5度点, 第2圈上的点均为6度点, 第3圈上的点均为3度点.图中所有点均为饱和点, 除一个为次大度点外, 0-点均为最大度点.若要图中0-点变为1-点或不定义点, 至少需去掉3条0-边, 而将其放在任何位置, 0-点个数必将增加, 1-点个数必将减少, 从而 $ \max\{ EBI(C_{3^3}\times P_{3_3})\}=27. $

引理3.3  若 $m\equiv 3($mod $4)$即 $m=3+4t$时, 那么幂圈嵌套图 $C_{3^m}\times P_{m_3}(m\ge 3)$的最大边-平衡指数为 $3^m$.

证  当 $m=3$时, 由引理3.2知公式成立.

下证 $m>3$时公式成立.

首先, 给出最大边-平衡指数对应标号图的构造方法.

由引理3.1知, 当 $m=3+4t$时带齿套圈子图 $T_i(i=1, 2, \cdots, \frac {m-3}{4})$的起点所在圈为 $\partial=3+4(i-1)$, 故其最大的边-平衡指数为 $3^{3+4i}-3^{3+4(i-1)}$.将引理3.2中 $m=3$时得到的最大边-平衡指数标号图作为基础图.依次按照引理3.2中带齿套圈子图 $T_i(i=1, 2, \cdots, \frac {m-3}{4})$的最大边-平衡指数标号图从里到外进行标号, 即可得到 $C_{3^m}\times P_{m_3}(m\ge 3)$的最大边-平衡指数标号图.

事实上, 在标号过程中图中点的特征均未发生变化, 依然满足友好标号, 故

$ \begin{eqnarray*} \max\{EBI(C_{3^m}\times P_{m_3})\}&=&\max\{EBI(C_{3^3}\times P_{3_3})\}+\sum\limits_{i=1}^t \max\{EBI(T_i)\}\nonumber\\ &=&3^3+(3^7-3^3)+(3^{11}-3^7)+\cdots+(3^m-3^{m-4}) \nonumber\\ &=&3^m(m>3), \end{eqnarray*} $

即若 $m\equiv 3($mod $4)$时, 那么 $ \max\{EBI(C_{3^m}\times P_{m_3})\}=3^m $.

引理3.4  在幂圈嵌套图 $C_{3^4}\times P_{4_3}$中, 最大的边-平衡指数为 $3^4$即81.

证  首先, 构造具有最大边-平衡指数的标号图.

由于幂圈嵌套图由路形图和幂圈图嵌套得到, 方便起见, 我们在路形图和幂圈套图中分别标号.

在路形图中, 将路径 $(2)_b(3)_c(4)_d(b=1, 2, 3, 4, 5, 6; c=3, 4, \cdots, 17;\ d=7, 8, \cdots, 51)$中的边和边 $(1)_1(2)_2, (1)_1(2)_3, (1)_2(2)_4, (1)_2(2)_5, \ (1)_3(2)_7, \ (1)_3(2)_9$为0 -边, 其余各边均为1 -边.

在幂圈套图中, 将第2圈上除边 $(2)_9(2)_1, \ (2)_6(2)_7$外其他标号为0, 第三圈上边均为0-边, 第4圈上的边 $(4)_i(4)_{i+1}(i=1+2r, \ 1\leq i\leq 5)$和 $(4)_i(4)_{i+1}(i=81-2r, \ 52\leq i\leq 81)$标号为0, 其它边则都标号为1.

经计算上述构造图满足边友好标号, 在图中 $(2)_i(i=2, 3, 4, 5), (3)_i(i=3, 4, \cdots, 17)$为0-点, 点 $(2)_6$为无定义点, 其它顶点都为1-点, 通过计算可得在图中共有19个0-点, 1个无定义点, 而图中共有120个点, 这样就得到 $ |v(0)-v(1)|=81. $

在上述构造图中, 第一圈上的点均为5度点, 第4圈上的点均为3度点, 其他圈上的点均为6度点.图中所有点均为饱和点, 且0-点均为6度点, 若要图中0-点变为1-点或不定义点, 至少需去掉3条0-边, 而将其放在任何位置, 0-点个数必将增加, 1-点个数必将减少, 从而 $ \max\{ EBI(C_{3^4}\times P_{4_3})\}=81 $.

引理3.5  若 $m\equiv0($mod 4 $)$即 $m=4+4t$时, 那么幂圈嵌套图 $C_{3^m}\times P_{m_3}(m\ge 3)$的最大边-平衡指数为 $3^m$.

证  当 $m=4$时, 由引理3.4知公式成立.

下证 $m>4$时公式成立.

首先, 给出最大边-平衡指数对应的标号图的构造方法.

由引理3.1知, 当 $m=4+4t$时带齿套圈子图 $T_i(i=1, 2, \cdots, \frac {m-4}{4})$的起点所在圈为 $\partial=4+4(i-1)$, 故其最大的边-平衡指数为 $3^{4+4i}-3^{4+4(i-1)}$.将引理3.4中 $m=4$时得到的最大边-平衡指数标号图作为基础图.依次按照引理3.1中带齿套圈子图 $T_i(i=1, 2, \cdots, \frac {m-4}{4})$的最大边-平衡指数标号图从里到外进行标号, 即可得到 $C_{3^m}\times P_{m_3}(m\ge 3)$的最大边-平衡指数标号图.

事实上, 在标号过程中图中点的特征均未发生变化, 依然满足友好标号, 故

$ \begin{eqnarray*} \max\{EBI(C_{3^m}\times P_{m_3})\}&=&\max\{EBI(C_{3^4}\times P_{4_3})\}+\sum\limits_{i=1}^t \max\{EBI(T_i)\}\nonumber\\ &=&3^4+(3^8-3^4)+(3^{12}-3^8)+\cdots+(3^m-3^{m-4}) \nonumber\\ &=&3^m(m>4). \end{eqnarray*} $

即若 $m\equiv 0($mod4 $)$时, 那么 $ \max\{EBI(C_{3^m}\times P_{m_3})\}=3^m $.

引理3.6  在幂圈嵌套图 $C_{3^5}\times P_{5_3}$中, 最大的边-平衡指数为 $3^5$即243.

证  首先, 对图 $C_{3^5}\times P_{5_3}$按照带齿套圈子图的定义, 将第一圈的边分离出可从中得到一个以第一圈上点作为起始点, 第5圈上点作为终点的套圈子图, 记作 $T_0$.按照引理3.1中对于带齿套圈子图的标号方法, 将 $T_0$进行标号, 再将第1圈上边 $(1)_1(1)_2$标号为0, 其它边则都标号为1.

经计算上述构造图满足边友好标号, 其中所有的0-点均在在 $T_0$中, 经过计算可知共有60个0-点, 而图 $C_{3^5}\times P_{5_3}$共有363个点, 这样就得到 $ |v(0)-v(1)|=243. $

在上述构造的标号图中, 第一圈上的点均为5度点, 第5圈上的点均为3度点, 其他圈上的点均为6度点.在上述标号下, 图中所有点均为饱和点, 且0-点均为6度点, 若要图中0 -点变为1 -点或不定义点, 至少需去掉3条0 -边, 而将其放在任何位置, 0 -点个数必将增加, 1 -点个数必将减少, 从而 $ \max\{ EBI(C_{3^4}\times P_{4_3})\}=243. $

引理3.7  若 $m\equiv1($mod 4 $)$即 $m=5+4t$时, 那么幂圈嵌套图 $C_{3^m}\times P_{m_3}(m\ge 3)$的最大边-平衡指数为 $3^m$.

证  当 $m=5$时, 由引理3.6知公式成立.

下证 $m>5$时公式成立.

首先, 给出最大边-平衡指数对应标号图的构造方法.

由引理3.1知, 当 $m=5+4t$时带齿套圈子图 $T_i(i=1, 2, \cdots, \frac {m-5}{4})$的起点所在圈为 $\partial=5+4(i-1)$, 故其最大的边-平衡指数为 $3^{5+4i}-3^{5+4(i-1)}$.将引理3.6中 $m=5$时得到的最大边-平衡指数标号图作为基础图.依次按照引理3.1中带齿套圈子图 $T_i(i=1, 2, \cdots, \frac {m-5}{4})$的最大边-平衡指数标号图从里到外进行标号, 即可得到 $C_{3^m}\times P_{m_3}(m\ge 3)$的最大边-平衡指数标号图.

事实上, 在标号过程中图中点的特征均未发生变化, 依然满足友好标号, 故

$ \begin{eqnarray*} \max\{EBI(C_{3^m}\times P_{m_3})\}&=&\max\{EBI(C_{3^5}\times P_{5_3})\}+\sum\limits_{i=1}^t \max\{EBI(T_i)\}\nonumber\\ &=&3^5+(3^9-3^5)+(3^{13}-3^9)+\cdots+(3^m-3^{m-4}) \nonumber\\ &=&3^m(m>5). \end{eqnarray*} $

即若 $m\equiv1($mod 4 $)$时, 那么 $ \max\{EBI(C_{3^m}\times P_{m_3})\}=3^m. $

引理3.8  在幂圈嵌套图 $C_{3^6}\times P_{6_3}$中, 最大的边-平衡指数为 $3^6$即729.

证  首先, 构造具有最大边-平衡指数的图形:

由于幂圈嵌套图由路形图和幂圈套图嵌套得到, 方便起见, 我们在路形图和幂圈套图中分别标号.

在路形图中, 将路径

$ \begin{eqnarray*}&& (2)_a(3)_b(4)_c(5)_d(6)_e(1\leq a\leq 9;\\ && b=2+3r, \ 1\leq b\leq 27;\\ && c=4+r+9s, \ r=0, 1, 2, \ 1\leq c\leq 81;\ d=10+r+27s, \ r=0, 1, \cdots , 8, \ 1\leq d\leq 243;\\ && e=28+r+81s, \ r=0, 1, \cdots, 26, \ 1\leq e\leq 729 )\end{eqnarray*} $

和路径

$ \begin{eqnarray*}&& (3)_b(4)_c(5)_d(6)_e( b=1+3r, \ 4\leq b\leq 9;\\ && c=3+9s, \ 12\leq c\leq 81;\ d=7+r+27s, \ r=0, 1, 2, \ 34\leq d\leq 243;\\&& e=19+r+81s, \ r=0, 1, \cdots, 8, \ 100\leq e\leq 729)\end{eqnarray*} $

以及

$ \begin{eqnarray*}&& (3)_b(4)_c(5)_d(6)_e( b=3+3r, \ 1\leq b\leq 8;\\ && c=7+9s, \ 1\leq c\leq 78;\ d=19+r+27s, \ r=0, 1, 2, \ 1\leq d\leq 243;\\ && e=55+r+81s, \ r=0, 1, \cdots, 8, \ 100\leq e\leq 702)\end{eqnarray*} $

中的边和边 $(1)_1(2)_2, \ (1)_2(2)_5, \ (1)_3(2)_8, \ (1)_3(2)_9$标为0 -边, 其余各边均为1 -边.

在幂圈套图中, 第6圈上

$ \begin{eqnarray*}&& (6)_i(6)_i+1(i=2+2r, \ 2\leq i\leq 27), \\ && (6)_i(6)_{i+1}(i=64+2r+81s, r=0, 1, \cdots, 17, \ 27\leq i\leq 702), \\ && (6)_i(6)_{i-1}(i=728-2r, \ 702\leq i\leq 729) \end{eqnarray*} $

和 $(6)_{729}(6)_1$为0 -边.第四圈和第五圈上的边均为0-边.另外, 将第1圈上的边 $(1)_1(1)_2$和第2圈上的边 $(2)_3(2)_4, \ (2)_6(2)_7$标号为0, 其它边则都标号为1.

经计算上述构造图满足边友好标号, 其中顶点

$ \begin{eqnarray*}&& (3)_i(i=2+3r, \ 1\leq i \leq 27), \\ && (4)_i(i=12+s+9t, \ s=0, 1, 2, 3, 4, \ 1\leq i\leq 81), \\&& (4)_i(i=4+s+71t, \ s=0, 1, 2, 3, \ t=0, 1)\end{eqnarray*} $

以及

$ \begin{eqnarray*}&& (5)_{3i-r}(i=12+s+9t, \ s=0, 1, 2, 3, 4, \ t=0, 1, \cdots, 6;\ r=0, 1, 2), \\ && (5)_{3i-r}(i=4+s+71t, \ s=0, 1, 2, 3, \ t=0, 1;\ r=0, 1, 2)\end{eqnarray*} $

为0 -点, 仅有 $(2)_9$一个为无定义点, 其它顶点都为1 -点.通过计算可得在图中共有181个0 -点, 1个无定义点, 而图中共有1092个点, 这样就得到 $ |v(0)-v(1)|=729. $

在上述构造图中, 第一圈上的点均为5度点, 第6圈上的点均为3度点, 其他圈上的点均为6度点.图中所有点均为饱和点, 且0 -点均为6度点, 若要图中0 -点变为1 -点或不定义点, 至少需去掉3条0 -边, 而将其放在任何位置, 0 -点个数必将增加, 1 -点个数必将减少, 从而 $ \max\{ EBI(C_{3^4}\times P_{4_3})\}=729 $.

引理3.9  若 $m\equiv2($mod 4 $)$即 $m=6+4t$时, 那么幂圈嵌套图 $C_{3^m}\times P_{m_3}(m\ge 3)$的最大边-平衡指数为 $3^m$.

证  当 $m=6$时, 由引理3.8知公式成立.

下证 $m>6$时公式成立.

首先, 给出最大边-平衡指数对应标号图的构造方法

由引理3.1知, 当 $m=6+4t$时套圈子图 $T_i(i=1, 2, \cdots, \frac {m-6}{4})$的起点所在圈为 $\partial=6+4(i-1)$, 故其最大的边-平衡指数为 $3^{6+4i}-3^{6+4(i-1)}$.将引理3.8中 $m=6$时得到的最大边-平衡指数标号图作为基础图.依次按照引理3.1中带齿套圈子图 $T_i(i=1, 2, \cdots, \frac {m-6}{4})$的最大边-平衡指数标号图从里到外进行标号, 即可得到的最大边-平衡指数标号图.

事实上, 在标号过程中图中点的特征均未发生变化, 依然满足友好标号, 故

$ \begin{eqnarray*} \max\{EBI(C_{3^m}\times P_{m_3})\}&=&\max\{EBI(C_{3^6}\times P_{6_3})\}+\sum\limits_{i=1}^t \max\{EBI(T_i)\}\nonumber\\ &=&3^6+(3^{10}-3^6)+(3^{14}-3^{10})+\cdots+(3^m-3^{m-4}) \nonumber\\ &=&3^m(m>6), \end{eqnarray*} $

即若 $m\equiv2($mod 4 $)$时, 那么

$ \begin{eqnarray*} \max\{EBI(C_{3^m}\times P_{m_3})\}=3^m. \end{eqnarray*} $

由引理3.3, 引理3.5, 引理3.7, 引理3.9可得:

定理3.1  无限路幂圈嵌套图 $C_{3^m}\times P_{m_3}(m\ge 3)$的最大边-平衡指数为 $3^m$.

引理4.1  在图 $C_{3^m}\times P_{m_3}(m\ge 3)$中, 任意给定的带齿套圈子图 $T_t(t=1, 2, \cdots, \frac {m-i}{4})(i=3, 4, 5, 6)$中, 若路形图的起点记作第 $\partial$圈上的点, 从内到外依次经过的圈记为称为第 $\partial +1$圈, 第 $\partial+2$圈, 第 $\partial+3$圈, 第 $\partial+4$圈, 则该带齿套圈子图边-平衡指数可经过变换得到 $\{3^{\partial+4}-3^\partial-2, \ 3^{\partial+4}-3^\partial-4$, $\ 3^{\partial+4}-3^\partial-6, \ \cdots, \ 6, 4, 2, 0\} $.

证  将引理3.1中给出的标号图作为原始图, 依次在其基础上进行变换可以达到相应指数对应的标号图形.

第1步  依次将

$ \begin{eqnarray*}&& (\partial+3)_a(\partial+4)_b\\ &&\leftrightarrow (\partial+4)_b(\partial+4)_{b+1}(a=7+s+27t+81u, \ s=0, 1, \cdots, 14, \ t=0, 1, \ 1\leq a\leq 3^{\partial+3};\\ && b=19+r+3s+81t+243u, \ r=0, 1, \ s=0, 1, \cdots, 14, \ t=0, 1, \ 1\leq b\leq3^{\partial+4}), \end{eqnarray*} $

这样我们依次得到指数分别为 $\{3^{\partial+4}3^\partial-2, \ 3^{\partial+4}3^\partial-4, \ \cdots, 40\times3^\partial\}$的标号图.

第2步  依次将

$ \begin{eqnarray*}&& (\partial+3)_a(\partial+4)_b\\ && \leftrightarrow(\partial+4)_b(\partial+4)_{b+1}(a=61+s+81u, \ s=0, 1, \cdots, 12, \ 1\leq a\leq 3^{\partial+3};\\ && b=181+r+3s+243u, \ r=0, 1, \ s=0, 1, \cdots, 12, \ 1\leq b\leq 3^{\partial+4}), \end{eqnarray*} $

这样我们依次得到指数分别为 $\{40\times3^\partial-2, \ 40\times3^\partial-4, \ \cdots, \ 68\times3^{\partial-1}\}$的标号图.

第3步  依次将

$ \begin{eqnarray*}&& (\partial+3)_a(\partial+3)_{a+1}\\ && \leftrightarrow(\partial+3)_a(\partial+4)_{b+1}(a=1+r+21s+27t, \ r=0, 1, 2, 3, 4, \ s=0, 1, \ 1\leq a\leq 3^{\partial+3};\\ && b=3+3r+64s+81t, \ r=0, 1, 2, 3, 4, \ s=0, 1, \ 1\leq b\leq 3^{\partial+4}), \end{eqnarray*} $

这样我们依次得到指数分别为 $\{68\times3^{\partial-1}-2, \ 68\times3^{\partial-1}-4, \ \cdots, \ 8\times3^{\partial-1}\}$的标号图。

第4步  依次将

$ \begin{eqnarray*} && (\partial+3)_a(\partial+3)_{a+1}\\ && \leftrightarrow(\partial+3)_a(\partial+4)_{b+1}(a=74+r+81s, \ r=0, 1, 2, \ 1\leq a\leq 3^{\partial+3};\\ && b=222+r+243s, \ r=0, 1, \ 1\leq b\leq 3^{\partial+4}), \end{eqnarray*} $

这样我们依次得到指数分别为 $\{8\times3^{\partial-1}-2, \ 68\times3^{\partial-1}-4, \ \cdots, \ 4\times3^{\partial-1}\}$的标号图.

第5步  依次将

$ (\partial+4)_b(\partial+4)_{b+1}\leftrightarrow(\partial+4)_b(\partial+4)_{b-1} (b=220+243s, \ 1\leq b\leq 3^{\partial+4}), $

这样我们依次得到指数分别为 $\{4\times3^{\partial-1}-2, \ 4\times3^{\partial-1}-4, \ \cdots, \ 2\times3^{\partial-1}\}$的标号图.

第6步  依次将

$ (\partial+4)_b(\partial+4)_{b+1}\leftrightarrow(\partial+4)_{b+1}(\partial+4)_{b+2} (b=224+243s, \ 1\leq b\leq 3^{\partial+4}), $

这样我们依次得到指数分别为 $\{2\times3^{\partial-1}-2, \ 2\times3^{\partial-1}-4, \ \cdots, \ 2, 0\}$的标号图.

由于在上述变换中每条边的变换均增加一个1-点, 而0-点个数不变, 故每次变换使指数减少2, 每一步都是在上一步的基础上进行变换, 综上即可证明.

推论4.1  带齿套圈子图 $T_t(t=\frac {m-i}{4})(i=3, 4, 5, 6)$的边-平衡指数可以依次变换至0.

证  在带齿套圈子图 $T_t(t=\frac {m-i}{4})(i=3, 4, 5, 6)$中嵌套不改变换点性质, 在带齿套圈子图中总可以找到一个变换后产生一个不定义点, 使指数减少1, 再由引理3.10可将其平衡指数变换至0.

引理4.2  在无限路幂圈嵌套图 $C_{3^m}\times P_{m_3}(m\ge 3)$中, 当 $m\equiv3($mod4 $)$时,

$ \begin{eqnarray*} \{3^m-1, \ 3^m-2, \ \cdots, \ 2, 1, 0\}\subset EBI(C_{3^m}\times P_{m_3}). \end{eqnarray*} $

证  当 $m=3$时, 将引理3.2中构造的最大边-平衡指数对应的标号图作为原始图.

先对偶数指数集进行构造：

第1步  将 $(1)_1(1)_2\leftrightarrow(1)_1(2)_1$得到指数为26的标号图.

第2步  将 $(2)_1(2)_2\leftrightarrow(2)_1(3)_3$, $(2)_8(2)_9\leftrightarrow(2)_8(3)_{24}$和 $(2)_9(2)_1\leftrightarrow(2)_9(2)_{27}$依次得到3个标号图, 边-平衡指数分别为 $\{24, \ 22, \ 20\}$.

第3步  依次将

$ (2)_a(3)_b\leftrightarrow(3)_b(3)_{b+1}(a=3, 4, 5, 6, 7;\ b=7+r+3s, \ r=0, 1, \ 7\leq b \leq 21) $

得到10个偶数指数的标号图, 指数分别为 $\{18, \ 16, \ \cdots, \ 2, 0\}$.

另外奇数指数集构造如下:

省去第一步, 重复偶数指数构造中2, 3步即可得到指数为 $\{25, \ 23, \ \cdots, \ 3, 1\}$的标号图.

即证公式成立.

当 $m>3$时, 下面变换是将引理3.3中构造的最大边-平衡指数对应的标号图作为原始图.

第1步  依次将图中套圈子图 $T_t(t=\frac {m-3}{4})$中的边 $(\partial+1)_b(\partial+1)_{b+1}\leftrightarrow(\partial)_a(\partial+1)_b(1\leq a\leq 3^{\partial}$; $\ b=1+3r, \ 1\leq b\leq 3^{\partial+1})$每次将一个1 -点变为不定义点, 0 -点个数不变, 经计算共有 $3^{m-4}$次变换, 故将得到指数分别为 $\{3^m-1, \ 3^m-2, \ \cdots, \ 3^m-3^{m-4}\}$的标号图.

第2步  根据推论4.1, 依次将图中套圈子图 $T_t(t=\frac {m-3}{4})$中边进行变换, 可以得到指数分别为 $\{3^m-3^{m-4}-1, \ \cdots, \ 1, 0\}$的标号图.

综上即可证明

$ \begin{eqnarray*} \{3^m-1, \ 3^m-2, \ \cdots, \ 2, 1, 0\}\subset EBI(C_{3^m}\times P_{m_3}). \end{eqnarray*} $

引理4.3  在无限路幂圈嵌套图 $C_{3^m}\times P_{m_3}(m\ge 3)$中, 当 $m\equiv0($mod4 $)$时,

$ \begin{eqnarray*} \{3^m-1, \ 3^m-2, \ \cdots, \ 2, 1, 0\}\subset EBI(C_{3^m}\times P_{m_3}). \end{eqnarray*} $

证  当 $m=4$时, 将引理3.4中构造的最大边-平衡指数对应的标号图作为原始图。首先对偶数指数集进行构造：

第1步  将 $(1)_1(2)_2\leftrightarrow(1)_1(2)_1$得到指数为80的标号图.

第2步  将 $(3)_1(3)_2\leftrightarrow(3)_1(4)_1$可得到指数为78的标号图.

第3步  依次将 $(3)_a(3)_{a+1}\leftrightarrow(3)_a(4)_b$ $(a=18+r;\ b=52+3r, \ r=0, 1, \cdots, 8)$得到9个偶数指数的标号图, 指数分别为 $\{76, 74, \ \cdots, \ 62, \ 60\}$.

第4步  依次将 $(3)_a(4)_b\leftrightarrow(4)_b(4)_{b+1}$ $(a=3+r;\ b=7+r+3s, \ r=0, 1, \ s=0, 1, \cdots, 14)$得到30个偶数指数的标号图, 指数分别为 $\{58, \ 56, \ \cdots, \ 2, \ 0\}$.

奇数指数集构造如下:

省去第一步, 重复偶数指数构造中2, 3, 4步即可得到指数为 $\{79, \ 78, \ \cdots, \ 3, \ 1\}$的标号图.

即证公式成立.

当证 $m>4$时, 下面变换是将引理3.5中构造的最大边-平衡指数对应的标号图作为原始图.

第1步  依次将图中套圈子图 $T_t(t=\frac {m-4}{4})$中的边

$ (\partial+1)_b(\partial+1)_{b+1}\leftrightarrow(\partial)_a(\partial+1)_b(1\leq a\leq 3^{\partial};\ b=1+3r, \ 1\leq b\leq 3^{\partial+1}), $

每次将一个1-点变为不定义点, 0-点个数不变, 经计算共有 $3^{m-4}$次变换, 故将得到指数分别为 $\{3^m-1, \ 3^m-2, \ \cdots, \ 3^m-3^{m-4}\}$的标号图.

第2步  根据推论3.1, 依次将图中套圈子图 $T_t(t=\frac {m-4}{4})$中边进行变换, 可以得到指数分别为 $\{3^m-3^{m-4}-1, \ \cdots, \ 1, 0\}$的标号图.

综上即可证明

$ \begin{eqnarray*} \{3^m-1, \ 3^m-2, \ \cdots, \ 2, 1, 0\}\subset EBI(C_{3^m}\times P_{m_3}). \end{eqnarray*} $

引理4.4  在无限路幂圈嵌套图 $C_{3^m}\times P_{m_3}(m\ge 3)$中, 当 $m\equiv 1($mod4 $)$时,

$ \begin{eqnarray*} \{3^m-1, \ 3^m-2, \ \cdots, \ 2, 1, 0\}\subset EBI(C_{3^m}\times P_{m_3}). \end{eqnarray*} $

证  当 $m=5$时, 将引理3.6中构造的最大边-平衡指数对应的标号图作为原始图.

首先对偶数指数集进行构造:

第1步  将 $(1)_1(1)_2\leftrightarrow(1)_1(2)_1$得到指数为242的标号图.

第2步  将 $(1)_3(2)_8\leftrightarrow(1)_3(1)_1$得到指数为240的标号图.

第3步  由引理3.10, 令 $\partial=2$得到一个带齿套圈子图, 按照引理3.10依次变换可以得到指数分别为 $\{238, 236, \cdots, 2, 0\}$的标号图.

奇数指数集构造如下:

省去第一步, 重复偶数指数构造中2, 3, 4步即可得到指数为 $\{241, \ 239, \ \cdots, \ 3, \ 1\}$的标号图.

即证公式成立.

当 $m>5$时, 下面变换是将引理3.7中构造的最大边-平衡指数对应的标号图作为原始图.

第1步  依次将图中套圈子图 $T_t(t=\frac {m-5}{4})$中的边

$ (\partial+1)_b(\partial+1)_{b+1}\leftrightarrow(\partial)_a(\partial+1)_b(1\leq a\leq 3^{\partial};\ b=1+3r, \ 1\leq b\leq 3^{\partial+1}), $

每次将一个1-点变为不定义点, 0-点个数不变, 经计算共有 $3^{m-4}$次变换, 故将得到指数分别为 $\{3^m-1, \ 3^m-2, \ \cdots, \ 3^m-3^{m-4}\}$的标号图.

第2步  根据推论3.1, 依次将图中套圈子图 $T_t(t=\frac {m-5}{4})$中边进行变换, 可以得到指数分别为 $\{3^m-3^{m-4}-1, \ \cdots, \ 1, 0\}$的标号图.

综上即可证明

$ \begin{eqnarray*} \{3^m-1, \ 3^m-2, \ \cdots, \ 2, 1, 0\}\subset EBI(C_{3^m}\times P_{m_3}). \end{eqnarray*} $

引理4.5  在无限路幂圈嵌套图 $C_{3^m}\times P_{m_3}(m\ge 3)$中, 当 $m\equiv 2($mod4 $)$时,

$ \begin{eqnarray*} \{3^m-1, \ 3^m-2, \ \cdots, \ 2, 1, 0\}\subset EBI(C_{3^m}\times P_{m_3}). \end{eqnarray*} $

证  当 $m=6$时, 将引理3.8中构造的最大边-平衡指数对应的标号图作为原始图.

首先对偶数指数集进行构造:

第1步  将 $(1)_1(1)_2\leftrightarrow(1)_1(2)_1$得到指数为728的标号图.

第2步   $(1)_2(2)_5\leftrightarrow(1)_2(1)_3$和 $(2)_3(2)_4\leftrightarrow(2)_3(1)_1$, 依次得到2个标号图, 边-平衡指数分别为 $\{726, \ 724\}$.

第3步  依次将

$ (5)_a(5)_{a+1}\leftrightarrow(5)_a(6)_b(a=1+r+213s;\ b=1+3r+639s, \ r=0, 1, \cdots, 7, \ s=0, 1) $

得到16个偶数指数的标号图, 指数分别为 $\{722, \ 720, \ \cdots, \ 694, \ 692\}$.

第4步  依次将

$ (5)_a(5)_{a+1}\leftrightarrow(5)_a(6)_b\\ (a=64+r+81s;\ b=190+3r+243s, \ r=0, 1, \cdots, 10, \ s=0, 1, \cdots, 7), $

这样就可分别得到88个指数为 $\{690, \ 688, \ \cdots, \ 518, \ 516\}$的标号图.

第5步  依次将

$ (5)_a(6)_b\leftrightarrow(5)_a(6)_b\\ (a=10+s+213t;\ b=28+r+2s+639t, \ r=0, 1, \ s=0, 1, \cdots, 11, \ t=0, 1), $

这样得到48个指数分别为 $\{514, \ 512, \ \cdots, \ 422, \ 420\}$的标号图.

第6步  依次将

$ (5)_a(6)_b\leftrightarrow(5)_a(6)_b\\ (a=34+s+213t;\ b=100+r+2s+243t, \ r=0, 1, \ s=0, 1, \cdots, 11, \ t=0, 1), $

这样得到210个指数分别为 $\{418, \ 416, \ \cdots, \ 2, \ 0\}$的标号图.

奇数指数集构造如下:

省去第一步, 重复偶数指数构造中2, 3, 4, 5, 6步即可得到指数为 $\{727, \ 726, \ \cdots, \ 3, \ 1\}$的标号图.

即证公式成立.

当证 $m>6$时, 下面变换是将引理3.9中构造的最大边-平衡指数对应的标号图作为原始图.

第1步  将图中套圈子图 $T_t(t=\frac {m-6}{4})$中的边

$ (\partial+1)_b(\partial+1)_{b+1}\leftrightarrow(\partial)_a(\partial+1)_b(1\leq a\leq 3^{\partial};\ b=1+3r, \ 1\leq b\leq 3^{\partial+1}), $

每次将一个1-点变为不定义点, 0-点个数不变, 经计算共有 $3^{m-4}$次变换, 故将得到指数分别为 $\{3^m-1, \ 3^m-2, \ \cdots, \ 3^m-3^{m-4}\}$的标号图.

第2步  根据推论3.1, 依次将图中套圈子图 $T_t(t=\frac {m-6}{4})$中边进行变换, 可以得到指数分别为 $\{3^m-3^{m-4}-1, \ \cdots, \ 1, 0\}$的标号图.

综上即可证明

$ \begin{eqnarray*} \{3^m-1, \ 3^m-2, \ \cdots, \ 2, 1, 0\}\subset EBI(C_{3^m}\times P_{m_3}). \end{eqnarray*} $

由引理4.2, 引理4.3, 引理4.4, 引理4.5得

定理4.1  在无限路幂圈嵌套图 $C_{3^m}\times P_{m_3}(m\ge 3)$中,

$ \begin{eqnarray*} \{3^m-1, \ 3^m-2, \ \cdots, \ 2, 1, 0\}\subset EBI(C_{3^m}\times P_{m_3}). \end{eqnarray*} $

由定理3.1和定理4.1得到如下定理:

定理5.1  在无限路幂圈嵌套图 $C_{3^m}\times P_{m_3}(m\ge 3)$,

$ \begin{eqnarray*} EBI(C_{2^m}\times P_{m_2})=\{3^m, 3^m-1 \cdots, \ 2, \ 1, \ 0\}. \end{eqnarray*} $