基于超立方体和圈的细胞分裂生长网络及其性质

常立婷+师海忠

摘要：立方连通圈是超立方体的有界变型，在这篇文章中作者以立方连通圈网络CCC（n）（n>2）为基础设计了一种新网络一CCC（n，k）（n>2且k是非负数），它是3正则3连通的，且有许多好的性质。作者证明了CCC（3，0）是哈密尔顿连通图，且CCC（n，k）（n>2且k是非负数）是哈密尔顿图，但当k>2和n>2或者k=l和22且k是非负数）和C_m的笛卡尔积的一些性质。

关键词：立方连通圈；CCC（n，k）；哈密尔顿图；哈密尔顿连通图；点可迁的

当且仅当，或者：

（i）x=y且/i-j/；l（modn）

（ii）i=j且x和y恰有第i个指标不同。

图1表示了Q₃到CCC（3）的变化

定义3^/10/：若一个图具有这样的一个图形，它的边仅在端点处相交，则该图称为平面图。

定义4^/10/：G的Hamilton圈是指包含G的每个顶点的圈。

定义5^/10/： -个图若包含Hamilton圈，则称这个图是Hamilton图。

定义6^/10/：若一个图中任意两个顶点之间都有一条Hamilton路，则称这个图为Hamilton连通图。

定义7^/9/：如果G是点可迁的，那么对G的每对顶点x和y，存在0∈Aut（G），使得y=0（x）。

定义8^/9/：设Γ=（X，o）是非平凡有限群，S是X的非空子集，且不含的r单位元e，定义有向图如下：V（G）=Γ ；（x，y）∈E（G）<=>x^-1 y∈S，x，y∈r称G为Γ 关于S的Cayley图，记为C_r（S）。

定义9：两个无向图G=（V，E）和G'=（V'，E'），这里V={μ₁，μ₂，…μ_/v'/）和V'={v₁，v₂，…v_/v'/），G和G'的笛卡尔积定义为无向图GxG'，其中顶点集为{μv/μ∈V，v∈V'），

边集为{（μv，μ'v'）I（μ=μ'，（v，v'）∈E'或（v=v'，（μ，μ'）∈E'））.

定義10：用3长的圈C₃=（0，1，2）代替CCC（n）的每个顶点，且C3中每个顶点仅位于CCC（n）中与该顶点关联的一条边上，我们得到新网络CCC（n，1）；用3长的圈C3 =（0，1，2）代替CCC（n，1）的每个顶点，且C3中每个顶点仅位于CCC（n，1）中与该顶点关联的一条边上，我们得到新网络CCC（n，2）；重复k次，我们得到新网络CCC，（n，k）。

2 CCC（3，0）的哈密尔顿连通性

引理2.1[9]：CCC（n）是点可迁的。

定理2.1： CCC（3，0）是哈密尔顿连通图。

证明：CCC（3，0）即为CCC（3），故我们要证的是CCC（3）是哈密尔顿连通图。由引理2.1知CCC（3）是点可迁的，所以我们只需找到（000；0）到（000；1）和（000；2）；（000；1）到（000；2）以及（000；0）：（000；1）和（000；2）分别到（010；0）、（010；1）、（010.2）、（10l；0）、（101；1）、（101；2）、（111；0）、（111；1）、（111；2）的一条Hamilton路即可。3 CCC（n，k）（n≥3，k≥0）的一些性质

引理3.1^[9]：CCC（3）是平面图；（如图2所示）

引理3.2^[9]： CCC（n）是Hamilton图

引理3.3^[9]：设G是n阶点可迁图，则

（a）G是正则的：

（b）G的所以n-l阶子图是同构的

引理3.4^[9]： Cayley图是点可迁的，但点可迁图不一定是Cayley图

引理3.5^[9]：设C是的CCC（n） -个圈，/（c）是圈C的长度，L（n）表示CCC（n）中所有圈的

集合，设l（c）∈{3，4，5，6，7}，则l（c）∈l（n），当且仅当/（c）=n

定理3.1： CCC（n，k（n≥3，k≥0）的一些性质：

（1） CCC（n，k）（n≥3，k≥0）有个n3^k2ⁿ”顶点，n3^k+12^n-1”条边；

（2 ）CCC（n，k）（n≥3，k≥0）是3正则3连通的；

（3） CCC（3，k）（k≥0）是平面图；

（4） CCC（n，k）（n≥3，k≥0）是Hamilton图；

（5） CCC（n，1）（3≤n≤7）不是点可迁的；

（6） CCC（n，1）（3≤n≤7）不是Cayley图；

（7） CCC（n，k）（n≥3，k≥2）不是点可迁图；

（8） CCC（n，k）（n≥3，k≥2）不是Cayley图。

证明：（1），（2）显然（3）由引理3.1知CCC（3）是平面图，故如图3 CCC（3，1）是平面图，依次下去可知CCC（3，k）（k≥0）是平面图；

（4）我们用数学归纳法证明结论

当时k=0，CCC（n，0）即为CCC（n），所以结论显然成立。

假设当k=r-l时，结论成立，即CCC（n，r -1）有一个哈密尔顿圈C_{ccc（n，r-1）}，则当k=r时设V则CCC（n，r-1）的任意顶点，v₁，v₂，V₃是与v相邻的三个顶点，则C_{ccc（n，r-1）}中必含边v₁v，V₂V，V₃V中的两条边。假设C_{ccc（n，r-1）}中含边v₁v，V₂。V₂v，（其他情况证明类似）（见图4），当用3长的圈代替CCC_{（n，r-1）}中的每个顶点时，我们假设用圈v_iv_iv_i代替v_i（o≤i≤3）。用圈v¹vv₂vv₃代替1，，则v，v₁，v₂，v₃四点处变化后的图为图5。用路p_v= （v³/₁，v³，v¹，v²，v²/₂）代替路（ V₁Vv₂）后，得到的圈C_{ccc（n，r-1）}即为CCC_（n，r）的一个哈密尔顿圈。

综上所述，由数学归纳法知CCC_（n，k）是哈密尔顿图。

（5）这里我们仅证明n=7的情况其余情况类似可说明，CCC（7）中必有图6所示结构，为了方便起见，我们将图中顶点分别标号l，2，…，n+l。

当用3长的圈代替CCC（7）中的每个顶点时，我们假设用圈i₁i₂i₃代替i（0≤i≤8），图6中结构变化后结构如图7，则图7中结构即为CCC（7，1）中的一部分不失一般性，设在CCC（7，1）中去掉顶点l，后得到的图为CCC'（7，1），而图7中结构所对的结构变为图8，CCC（7，1）中去掉顶点l，后得到的图为CCC'（n，k），而图7中结构所对的结构变为图9（注意为了方便起见，我们将CCC'（7，1）和CCC"（7，1）中的点分别加了表示“'”， “"”，且CCC（7，1）与CCC'（7，1）和CCC"（7，1）仅在图7部分不同，其余结构均相同）因此CCC'（7，1）中顶点除I'₂，I'₃，8'为2度顶点外，其余均為3度顶点，CCC"（7，1）除7"₃，l"₁，l"₃顶点为2度顶点外，除其余均为3度顶点，由引理3.3知我们只需证CCC'（7，1）与CCC"（7，1）不同构即可。假设CCC'（7，1）≌CCC"（7，1），即存在①使得Φ（a）=b_i（a_i∈V（ccc'（7，1））b_i∈V（CCC"（7，1）））

因为与顶点8'₁：相连的顶点8'₂：，8'₃均为3度顶点，而与顶点l"₁相连的顶点1"₃为2度顶点，与顶点l"₃相连的顶点1"₁：为2度顶点，故Φ（8'₁）≠1"₁且Φ（8'₁）≠l"₃， 因此Φ（8'₁）=7"₁， 即想要CCC'（7，1）≌CCC"（7，1），

由引理3.5知，在CCC（7）中l含在7长的基本圈12345671里，含1的其他圈均大于7，故在CCC（7，1）中l₂和I₃含在14圈1₂1₃2₂2₃3₂3₃4₂4₃5₂5₃6₂6₃7₂7₃1₂里，含l₂和l₃的长其他圈均大于14（除l₁1₂1₃），故在CCC'（7，1）中1'₂和l'₃含在14长圈l21：22233233424352536263727312里，而在CCC"（7，1）中含1"₁和l"₃的圈均大于14，即

综上所述，C，CC'（7，1）与CCC"（7，1）不是同构的， 即CCC（7，1）不是点可迁图。CCC_（n，1）（3≤n≤7）不是点可迁图。

（6）由引理3.4和（5）显然可得。

（7）当时k>2，CCC_（n，k）（n≥3）中必有图10所示结构，为了方便起见我们将图中顶点标记为1-18，不失一般性，我们不妨设在CCC_（n，k）中去掉顶点3后得到的图为CCC_（n，k），而图10中结构所对的结构变为图11，CCC_（n，k）中去掉顶点1后得到的图为CCC"_（n，k），而图10中结构所对的结构变为图12，（注意为了方便起见，我们将CCC'_（n，k）和CCC"_（n，k）中的点分别加了表示“'”，“"”，且CCC_（n，k）与CCC'_（n，k）和CCC"_（n，k）仅在图10部分不同，其余结构均相同）因此，CCC'_（n，k）除1'，2'，7'顶点为2度顶点外，其余均为3度顶点，CCC"_（n，k）除2"，3"，10"顶点为2度顶点外，其余均为3度顶点，由引理3.3知，我们只需证CCC'_（n，k）与CCC"_（n，k）不同构即可。假设CCC'_（n，k）兰endprint

CCC"_（n，k），即存在Φ使得Φ（a_i）=b_i∈V（CCC'_（n，k））），b_i∈V（CCC"_（n，k））））

因为与顶点7'相连的顶点8'，9'均为3度顶点，而与顶点2"相连的顶点3"为2度顶点，与顶点3"相连的顶点2"为2度顶点，故Φ（7"）≠2"且Φ（7'）≠3"，因此①（7'）=10"，即想要CCC'_（n，k）≌CCC"_（n，k）.

由图12显然2"4"6"8"7"3"2"为一个6长的圈，即CCC"_（n，k）中2"和3"在一个6长的圈中，而10'1'2'4'为4长的路，与顶点10'相连11'和12'的都不与与4'相连的5'和6'相连，故1'和2'不可能在一个6

综上所述，CCC，，（n，"与CCC，”（聆，”不是同构的，即CCC_（n，k）（k≥2）不是点可迁图。

（8）由引理3.4和（7）显然可得。4 CCC_（n，k）（k≥2）与圈C_m的笛卡尔积

引理4.1[9]：设G=（V，E）和G'=（V'，E'），GxG'为G和G'的笛卡尔积则

（1）如果G和G'分别为r正则和r'正则的，

则GxG'是r+r'正则的。

（2）如果κ（G）=δ（G）>0，κ（G'）=δ（G'）0，那么κ（G×G'）=κ（G）+κ（G'）

引理4.2[9]： Hamilton图的笛卡尔积是Hamilton图。根据文[13]和[14]，我们设计出了新的互连网络CCC_（n，k）（n≥3，k≥0×Cm。

引理4.3：如果G=（V，E）是哈密尔顿连通图，C_k为一个k长的圈，则G×C，k是哈密尔顿连通图。

证明：设G=（V，E）是哈密尔顿连通图，其中V={x₁，x₂：….，X_/V/}，C_k為k长的圈，其中V_c={y₁，y₂….，y_k}，定义GxC_k为G和C_k的笛卡尔积。设G_j= （V_j，E_j）为Gx C_k的子图。

其中Vj={xy_jx∈V.显然，G_j≌G。定义endprint