熊志坤，王广富

（1.华东交通大学理学院，江西 南昌330013；2.东莞市第七高级中学，广东 东莞523500；3.烟台大学数学与信息科学学院，山东 烟台 264005）

化学图论早在18 世纪下半叶被引入[1]，在1758年Cullen 和Black 绘制的第一个化学分子的示例图就代表了化学物质之间的相互作用。 Cullen 用化学图解释分子之间的化学反应，但可惜作为课堂笔记没有发表[2]。 在接下来的19 世纪50 年代和60 年代，结构理论[3]和化合价理论[4]逐渐成为化学图论研究的主流。 在20 世纪30 年代，化学图论发展还包括同分异构体计数[5]、拓扑指标[6-9]等关键领域。 在化学图论中，常把原子看作一个顶点，原子之间的化学键看作一条边。 只考虑分子图中的碳原子，不考虑氢原子和复杂的化学键.拓扑指标实际上就是考虑化学图上顶点之间的距离，在化学图上计算任意两点之间的距离十分复杂。 而在超立方体中的两点间距离就是Hamming 距离，可以极大地简化拓扑指标的计算[10]。Assouad 和Deza 证明了l1-图是可以按距离成倍数嵌入某个超立方体的图[11]。因此，研究图的l1-嵌入具有重要意义。

能够嵌入欧式平面使得不同边只在顶点处相交的图，称为平面图。 Deza 和Shtogrin[12]研究了平面上的若干化学分子图的l1-嵌入性，例如：苯、萘、联苯等可以l1-嵌入。 Deza 和Laurent[13]得到了一些可以l1-嵌入的图类，例如：鸡尾酒会图，半立方体，皮特森图等。 Deza 和Laurent[13]还得出2 个l1-图通过1 个顶点相粘后得到的新图也是l1-图。 Deza 和Grishuklin[14]证明了每个平面上的l1-图都可以2 规模地嵌入某个超立方体。 能够等距离地嵌入某个超立方体的图，称为部分立方体。 Klavzar 和Gutman[15]证明了所有苯环系统都是部分立方体。 张和平和徐守军[16]证明了带冠状的苯环系统都不是部分立方体。张和平和王广富[17]研究了开口纳米管的l1-嵌入性，在所有的开口纳米管中只有三类退化的情况才是部分立方体。 王广富和张和平[18]研究了莫比乌斯面上的六边形堆砌图中只有H2，2和H3，3是l1-图，莫比乌斯面上的四边形堆砌图中只有Q1，2是l1-图。王广富和Shpectorov[19]证明了一般的莫比乌斯面上的四边形堆砌图包含唯一的非零伦圈，同时刻画了可以l1-嵌入的莫比乌斯面上的四边形堆砌图的结构特征。李晨阳和王广富[20]证明了树、单圈图以及它们的线图都是l1-图。 王广富、李晨阳和王凤灵[21]得到了2 个l1-图的门和图还是l1-图。

环己烷类图上所有的点都是2 度或3 度，只有1 个4-边形面， 其他面都是6-边形。 Deza 和Shtogrin[12]证明了4-边形上都是3 度点的环己烷类图不是l1-图。 本文对环己烷类图4-边形上点的度进行分类：对于环己烷类图4-边形上只有2 个3 度点的情况，如果这2 个3 度点是相邻的，则称为第一型环己烷类图； 如果这2 个3 度点是相对的，则称为第二型环己烷类图。如果环己烷类图4-边形上有3 个3 度点， 称为第三型环己烷类图.证明了第一型环己烷类图是l1-图，第二型和第三型环己烷类图都不是l1-图。

1 预备知识

文中涉及的所有图都是有限的、简单的、没有自环的连通图。对于1 个图G，用V（G）和V（G）分别表示图G的顶点集和边集。 2 个点u 和v 之间连边，也称u 和v 相邻。 对于2 个图H 和G，如果V（E）⊆V（G）且E（H）⊆E（G），那么称图H 是图G 的子图。如果V′⊆V（G）且E′是由图G 上两端点都在V′中边所组成的边集， 称其为图G 的由V′导出的子图，记为G[V′]。 路是指1 个点不重复的点边交错序列，通常用P 表示。 起点和终点重合的路称为闭路，也叫做圈，通常用C 表示。设u 是图G 上的任一顶点，所有与u 相关联的点组成的集合称为点u 的邻域，记为N（u）。在N（u）中包含的顶点数称为点u 的度。设u 和v 是V（G）中的2 个点，u 和v 之间最短路的长度称为u 和v 之间的距离，用dG（u，v）表示。 在不引起歧义时，简记为d（u，v）。 则（V（G），d）构成1 个度量空间，称为图G 的伴随度量空间。 如果图G 的任意2 个点之间都存在1 条路，那么G 为连通图。 对于H 图上的任意2 个点u 和v 都有dG（u，v）=dH（u，v），那么图H 是图G 的等距离子图。

n 维超立方体Qn的点集是由所有n 元有序数组a1a2…an组成，其中ai∈{1，0}，（1≤i≤n）。 于是Qn有2n个顶点，2 个顶点相邻当且仅当它们对应的n元有序数组恰有1 个位置的元素不同。

1 个图G 称为l1-图（或l1-嵌入的），如果它的伴随度量空间与l1-空间的某个子空间同构。也就是说存在从（V（G），dG）到（X，d1）的1 个距离保持映射φ，对G 的任意2 个顶点x 和y，满足dG（x，y）=d1（φ（x），φ（y））。 Assouad 和Deza[11]证明了1 个图G 是l1-图当且仅当存在2 个正整数λ 和n，图G 可以λ倍地嵌入到某个超立方体Qn中。 即对任意的顶点x，y∈V（G），存在1 个映射φ：V（G）→V（Qn），满足λdG（x，y）=dQn（φ（x），φ（y））。

2 个简单图G 和H 同构，也就是说，它们的顶点集之间存在1 个双射，使得对于图G 的任意2 个点u 和v，存在图H 中的2 个点x 和y 与之对应，满足u 和v 在图G 中相邻当且仅当x 和y 在图H 中相邻，记作G≅H。

2 个图G 和H 的卡式积图G□H 的点集是V（G）×V（H），2 个顶点（u1，u2）和（v1，v2）相邻要么u1=v1且u2和v2在图H 中相邻， 要么u2=v2且u1和v1在图G 中相邻。

1 个具有k 条边的面，称为k-边形。至少包含1个边界顶点的面，称为边界面。 反之，所有点都是内点的面，称为内面。

定义1.1 单一4-边形环己烷类分子图是指嵌入到平面上的2 连通图，其中恰有1 个四边形面，其他都是六边形面，四边形面上的顶点度为2 或3，其余内点度为3，边界点度为2 或3。

下面引入几个常用的定理来判断图的l1-嵌入性。定理1.2[13]如果2 个简单连通图G 和H 都是l1-图，那么它们的卡式积图G□H 也是l1-图。

外可平面图G 是指其存在一种嵌入欧式平面的方式，使得所有边只在顶点处相交且所有顶点都在外平面上.常见的外可平面图有：路，圈等。

定理1.3[14]任意一个外可平面图都是可以l1-嵌入的。

对于l1-图，有一个非常重要的必要条件是：定理1.4[22]对于1 个连通图G，如果它是l1-图，对于图G 上任意5 个点x，y，a，b，c，那么dG一定满足下面的5-边形不等式：d（x，y）＋d（a，b）＋d（b，c）＋d（a，c）≤d（x，a）＋d（x，b）＋d（x，c）＋d（y，a）+d（y，b）＋d（y，c）。

从定理1.4 可以容易看出，若能够在图G 中找出5 个顶点，它们违反了5-边形不等式，则说明这个图不是l1-嵌入的。

2 单一4-边形环己烷类分子图的l1-嵌入性

单一4-边形环己烷类分子图上恰有1 个4-边形，其上的顶点度为2 或3，本小节研究单一4-边形环己烷类分子图的l1-嵌入性， 下面对其4-边形上顶点的度进行分析。

定理2.1 单一4-边形环己烷类分子图的4-边形上至少有2 个3 度点。

证明

1） 如果单一4-边形环己烷类分子图的4-边形上都是2 度点，则该4-边形是孤立的，单一4-边形环己烷类分子图上不存在从4-边形到6-边形的路，与图的连通性相矛盾，故环己烷类图的4-边形上至少有1 个3 度点。

2） 如果单一4-边形环己烷类分子图的4-边形上只有1 个3 度点，不妨记为u，如图1 所示，则4-边形上另外3 个顶点都是2 度点。 通过u 向外发出一条边记为uu1， 要使得4-边形上的边被6-边形覆盖， 则由顶点u 出发的路经过若干个点后必须回到4-边形上异于u 的顶点。则与单一4-边形环己烷类分子图的4-边形上只有1 个3 度点相矛盾，故单一4-边形环己烷类分子图的4-边形上至少有2 个3 度点。

图1 环己烷类图的4-边形上只有一个3 度点Fig.1 Only one 3-degree vertex on the 4-cycles of the cyclohexane graph

单一4-边形环己烷类分子图的4-边形上至少有2 个3 度点， 那么其4-边形有可能是2 个3 度点，这2 个3 度点有两种位置关系，当这2 个3 度点相邻时，则称其为第一型环己烷类图，当这2 个3度点相对时， 则称其为第二型环己烷类图；4-边形上也可能有3 个3 度点， 当4-边形上有3 个3 度点， 称其为第三型环己烷类图；4-边形上也可能4个都是3 度点。 下面开始证明当4-边形上有2 个相邻3 度点的情况下，单一4-边形环己烷类分子图的l1-嵌入性。

引理2.2[12]如果单一4-边形环己烷类分子图的4-边形上都是3 度点，那么该图不是l1-图。

定理2.3 第一型环己烷类图是可以l1-嵌入的。

证明 设第一型环己烷类图G 的4-边形上任意2 个相邻的3 度点为u 和v，如图2 所示，4-边形上与u 和v 相关联的点分别记为a 和b。 通过u 和v分别向外发出1 条边， 产生2 个点分别记为u1和v1，再把u1和v1连边。得到由V′=（a，b，u，v，u1，v1）导出的子图，记为G[V′]。 此时G[V′]上除了uv 以外的边都被6-边形auu1v1vba 所覆盖一次。 通过u1和v1分别向外发出1 条边，产生的2 个点分别记为u2和v2，再把u2和v2连边。 如图3 所示，得到由V（G0）={a，b，u，v，u1，v1，u2，v2}导出的子图，记为G0。 此时图G0上所有的边可以被6-边形auu1v1vba 和uu1u2v2v1vu 覆盖1 次或2 次。在基图G0上通过u2和v2分别向外发出1 条边，产生2 个点分别记为u3和v3，再把u3和v3连边，依次类推把un和vn连边，得到第一型环己烷类图G。 不难看出第一型环己烷类图G 与梯子图（如图4 所示）同构。 而梯子图H=Pn+1□P2且由定理1.3 知任意路都是l1-图，通过定理1.2知梯子图H 是l1-图， 故第一型环己烷类图G 是可以l1-嵌入的。

图2 第一型环己烷类图GFig.2 The type I cyclohexane graph G

图3 G 图的导出子图G0Fig.3 The induced subgraph G0 of the graph G

图4 梯子图HFig.4 The ladder graph H

此时，证明了当单一4-边形环己烷类分子图的4-边形上有2 个相邻的3 度点时， 那么该图是l1-图。 下面证明4-边形上有2 个相对的3 度点时，单一4-边形环己烷类分子图的l1-嵌入性。

定理2.4 第二型环己烷类图不是l1-图。

证明：设第二型环己烷类图M 的4-边形上任意2 个相对的3 度点为x 和y， 如图5 所示4-边形上剩下的2 个2 度点不妨记为a 和b。 通过x 和y 分别向外发出1 条边， 产生的2 个点分别记为x1和y1，再由x1和y1分别向外发出两条边，产生2 个点记为c 和d。 如图6 所示，得到由V（M0）＝{a，b，c，d，x，y，x1，y1}导出的子图，记为M0。 此时，图M0上所有的边可以被6-边形xx1cy1ybx 和xx1dy2yax 覆盖1 次或2 次。 在图M0上通过c 和d 分别向外发出1 条边，产生的2 个点分别记为x2和y2，再由x2和y2分别向外发出2 条边， 产生2 个点记为x3和y3，依次类推，得到第二型环己烷类图M。 接下来考虑由V（H）＝{a，b，c，x，y，x1，y1}产生的导出子图H，不难验证在图H 中任取2 个点u 和v，都有dM（u，v）=dH（u，v）。 因此，图H 是图M 的等距离子图。 如图7所示，取图H 上的5 个顶点x，y，a，b，c，易得d（x，y）＝2，d（a，b）＝2；d（a，c）=3，d（b，c）=3；而d（x，a）=1，d（x，b）=1，d（x，c）=2，d（y，a）=1，d（y，b）=1，d（y，c）=2。 则d（x，y）+d（a，b）+d（a，c）+d（b，c）=10，而d（x，a）+d（x，b）+d（x，c）+d（y，a）+d（y，b）+d（y，c）=8。

图5 第二型环己烷类图MFig.5 The type Ⅱcyclohexane graph M

图6 图M 的导出子图M0Fig.6 The induced subgraph M0 of the graph M

图7 图M0 的导出子图HFig.7 The induced subgraph H of the graph M0

即在第二型环己烷类图M 上找到了5 个点x，y，a，b，c 违反5-边形不等式，使得：d（x，y）+d（a，b）+d（a，c）+d（b，c）＞d（x，a）+d（x，b）+d（x，c）+d（y，a）+d（y，b）+d（y，c）。 由定理1.4 知第二型环己烷类图M不是l1-图。

此时，证明了当单一4-边形环己烷类分子图的4-边形上有2 个相对的3 度点时，那么该图不是l1-图，下面证明当4-边形上有3 个3 度点时，单一4-边形环己烷类分子图的l1-嵌入性。

定理2.5 第三型环己烷类图不是l1-图。

证明：设第三型环己烷类图N 的4-边形上唯一的2 度点为w，如图8 所示，4-边形上与w 相对的3 度点为y，4-边形上剩下的两个3 度点不妨设为u和v。 由u，v，y 3 个点分别向外发出1 条边，产生的3 个点分别记为u1，v1和y1， 再由u1，v1和y1分别向外发出2 条边， 产生同时与u1和v1相关联的点记为z，与u1相关联的点记为a，同时与y1和a 相关联的点记为b，与v1相关联的点记为d，同时与y1和d相关联的点记为c。 此时，由V（N0）＝{a，b，c，d，u，v，w，y，z，u1，v1，y1}导出的子图，记为N0。 如图9 所示，图N0上所有的边可以被6- 边形aby1yuu1a，cdv1vyy1c 和vv1zu1uwv 覆盖1 次或2 次。接下来考虑由V（H）＝{u，v，w，y，z，u1，v1}产生导出的子图H，不难验证在图H 中任取2 个点m 和n, 都有dN（m，n）=dH（m，n）。 因此，图H 是图N 的等距离子图。 如图10 所示，取图H 上的5 个顶点u，v，w，y，z，不难得到d（u，v）=2，d（w，y）＝2，d（w，z）＝3；d（y，z）=3，而d（u，y）=1，d（u，w）=1，d（u，z）=2，d（v，y）=1，d（v，w）=1，d（v，z）=2。 则d（u，v）+d（w，y）+d（w，c）+d（y，z）=10，而d（u，y）+d（u，w）+d（u，z）+d（v，y）+d（v，w）+d（v，z）=8。

图8 第三型环己烷类图NFig.8 The type Ⅲcyclohexane graph N

图9 图N 的导出子图N0Fig.9 The induced subgraph N0 of the graph N

图10 图N0 的导出子图HFig.10 The induced subgraph H of the graph N0

即在第三型环己烷类图N 上找到了5 个点u，v，w，y，z 违反5-边形不等式，使得：d（u，v）+d（w，y）+d（w，z）+d（y，z）＞d（u，y）+d（u，w）+d（u，z）+d（v，y）+d（v，w）+d（v，z）。由定理1.4 知第三型环己烷类图N不是l1-图。

到此，本文证明了单一4-边形环己烷类分子图的4-边形上有2 个相邻的3 度点时， 那么该图是l1-图；其4-边形上有2 个相对的3 度点时，不是l1-图；其4-边形上有3 个3 度点时，也不是l1-图。 即单一4-边形环己烷类分子图中，除了第一型环己烷类图是l1-图，其他的都不是l1-图。