一种1-齐次图的完全分类.pdfVIP

第20卷第4期 纺 织 高 校 基 础 科 学 学 报 Vo1．20，NO．4 2007年12月 BASIC SCIENCES JOURNAL OF TEXTILE UNIVERSITIES Dec．，2007 *研究简报 * 文章编号：1006—8341(2007)04—0434—03 一 种1一齐次图的完全分类 耿智琳，张耀峰 (湖北经济学院 信息管理学院。湖北 武汉 430205) 摘要：对满足条件(i)对r中任意一边“ ，D (“， )是团，和条件(ii)对某个整数 (1 )， c 一 1且 a 一b ，且直径为d，价为k的齐次图r进行了完全分类． 关键词：距离正则图；交叉阵列；交叉数；齐次图 中图分类号：0 157．3 文献标识码：A 1 主要结果 设r是一个直径为d，价为k的距离正则图，记 (“， )一l P ， (“， )1．称 (“， )为r的交叉数， 记D；(“， )一 (“)n ( )且D(u， )一D{(“， )，并把集合{D；(“， ) 称作图r关于顶点“和 zcn 一 {主 1：i圣j ；卜 距离正则图r的交叉阵列是被r惟一确定的，反之不真．但是，对于部分距离正则图，与其交叉阵列是 收稿日期：2007—04—04 通讯作者：耿智琳(1980一)，女，河北省邯郸市人，湖北经济学院助教，硕士．E—mail：zyfgzl@l26．corn 第4期 一种1一齐次图的完全分类 435 一 -- x,1应的．关于距离正则图更详尽的性质见文献[4—5]． 下面给出 齐次图的定义． 定义3 连通图I1称作一个t一齐次图，如果对所有的整数r， ，i， 以及所有满足O(u， )一 (“ ， )：：： t的顶点u， ，“ ， ，结论 z∈D；(U， )，z ∈D；(U ， ) e(z，D：(“， ))：==e(x ，D (“ ， )) 成立，其中，e(3c，y)表示顶点z和顶点子集y之间的边数． 显然，一个0一齐次图就是距离正则图． 本文讨论的是 1一齐次图，得到下面的结论： 定理 1 设I1是一个直径为d，价为是的齐次图．若对I1中任意一边“， ，D (“，my)是团，且对某个 整数i (Oi )，满足c 一1且n 一b ，则下列之一成立： (1) 图r是一个Coxeter图且 i一3； (2) 图r是一个Biggs—Smith图且i=4，5，6； (3) 图r是一个十二面体且i一2，3． 2 预备知识 对l一齐次图的研究，在文献[6]中已得到了一些重要的结果： 设I1是一个1一齐次图，UO是图I1中一条固定的边，记D =D；(“， )．如果D ≠j2『，则每个诱导子图 Dj都是一个正则图． 命题1 r是一个距离正则图． 命题2 设 ∈D 且a是诱导子图D 的价，则 (1) e(x，D；)一Ⅱi—a； (2) e(x，D茸{)一Ⅱ斗l—a． 命题3口是诱导子图D 的价，则0≤Ⅱ 一a≤rain{C汁 一C ，n ／b 3 定理的证明 3．1 引理 如不特殊指出，图I1设为一个直径为d，价为是的1一齐次图，且满足条件：(1)对I1中任意一边UO， D (“， )是一个团；(2)对某个整数i (Oi )，满足f 一1且a 一b ．设诱导子图D 的价是a，由 命题3，马上得到引理1． 弓I理1 口一n 或a—n +1． 引理2 i≠1．进而，d≥3． 证明 假设 i一1． 情形(1) 若a—n +1．由命题2(1)知，V z∈D ，都有e(x，D )=1．任意取 ∈D{，则}D{l e(y， D})一}D；}e(x，Dj)，即n ·e(y，D{)一b ，从而n 一e(y，D；)．另一方面，又有n 一e(y，D )+e(y，Di) +e(y，D )≥e(y，D )+1，矛盾． 情形(2)