论文部分内容阅读
Johnson图J(n，k)的定义如下：设n，k是固定的正整数且满足n≥k，Ω是大小为n的固定的集合，那么J(n，k)的顶点集由Ω的所有k元子集组成，两个顶点相邻当且仅当这两个顶点对应的k元子集的交的大小为k-1．对于图G的一个顶点v，v的一个局部割是由v的邻点x或者边vx构成的大小为d(v)的集合。对于图G，设W(?)(V(G)∪E(G))，当G-W不连通或者只有一个顶点时，W就定义为图G的一个广义割；当G-W的直径大于图G的直径时，W就定义为图G的一个直径增长集．Daven和Rodger在1999年证明了J(n，k)的连通度是k(n-k)，在本文中，首先我们用更简单的方法证明了同样的结果．接着我们论证了当n≠4且k≠2时，J(n，k)的每一个最小广义割都是某个顶点的一个局部割；当k≠2时，或者n≠6且k≠3时，J(n，k)的每一个最小的直径增长集是某个顶点的一个局部割的子集．最后我们得到了当n≥3时，J(n，k)有—个哈密尔顿圈．