Johnson图的割集与哈密尔顿循环研究

90 浏览量更新于2024-09-03 收藏 259KB PDF 举报

"Cutsets and Hamiltonian cycles of Johnson graphs - Wantao Ning, Qiuli Li, Heping Zhang - Lanzhou University" 这篇论文主要研究了Johnson图的割集与哈密尔顿圈特性。Johnson图J(n,k)是图论中的一个重要概念，它是由所有大小为k的子集构成的，这些子集来自一个具有n个元素的集合Ω，且两个子集相邻当且仅当它们的交集大小为k-1。这个定义来源于组合数学，特别在编码理论、设计理论和图论中有广泛的应用。文章首先探讨了Johnson图J(n,k)中的局部割。对于图G中的一个顶点v，一个局部割是指大小为d(v)的集合，该集合包含v的邻接点x或边vx，这里的x也是v的邻接点。局部割在理解图的连通性和结构方面起着关键作用。接着，作者们引入了直径增长集的概念，这是图G中的一组顶点和边，当从图G中移除这组元素后，图的直径（任意两个顶点间的最短路径长度的最大值）会增加。这个概念有助于研究图的可遍历性和路径性质。论文的重点在于证明了除了J(4,2)之外，Johnson图J(n,k)的每一个最小的广义割都是局部割。这个结果深化了对Johnson图结构的理解，尤其是最小割集的特性。此外，他们还指出，在J(n,2)和J(6,3)之外的所有Johnson图中，最小的直径增长集都是局部割的一部分。这一发现可能对寻找这些图的哈密尔顿圈有直接影响。最后，作者们得出结论，对于n≥3的情况，Johnson图J(n,k)都含有哈密尔顿循环。哈密顿循环是图论中的一个经典问题，指的是图中能够遍历所有顶点且仅遍历一次的循环路径。这个结果对于证明Johnson图的连通性和结构特性至关重要。关键词：Johnson图，广义割，直径，哈密尔顿循环 AMS主题分类：05C40（图的路径和循环），05C12（图的特殊类），05C45（图的直径和其他度量）这篇论文属于图论领域的原创性工作，对理解和操作Johnson图提供了新的见解，特别是在割集和哈密尔顿循环的构造上。这些理论成果对于相关领域的研究者来说具有很高的价值。

connectivity of a graph G respectively. Ramras characterized smallest gen-

eralized cutset of a graph G (not complete) with equal connectivity and

edge-connectivity in the following lemma.

Lemma 2. [8] If G is a simple graph with κ(G) = κ

(G) < |V (G)| − 1, then

every smallest generalized cutset in G has size κ(G) and consists of a subset

of a minimum separating set and one edge incident to each remaining vertex

of that separating set. 2

Lemma 3. For each vertex v in J(n, k), J(n, k) − N[v] is connected.

Proof. For k = 1, J(n, 1) is a complete graph, the result is obvious.

For k ≥ 2, let v = {a

, a

, · · · , a

}. There exists a vertex ¯v = {a

k+1

, a

k+2

· · · , a

} such that |¯v

v| = 0 since n ≥ 2k. Clearly, ¯v /∈ N[v]. Now we

show that there exists a path from v

to ¯v for any vertex v

in J(n, k)− N[v].

Let v

= {b

, b

, · · · , b

}. Then v

, v

, · · · , v

k−1

, ¯v is a path from v

to ¯v,

where v

= {a

k+1

, a

k+2

, · · · , a

k+i

, b

i+1

, · · · , b

}, i = 1, 2, · · · , k − 1. Since v

not adjacent to v, v

contains at least two elements diﬀerent from v. Hence

each v

contains at least two elements diﬀerent from v, which implies that

/∈ N[v]. So J(n, k) − N[v] is connected for each vertex v. 2

Now, we give our main result of this section.

Theorem 4. Every smallest generalized cutset is a local cut in J(n, k) except

J(4, 2).

Proof. Let W be a smallest generalized cutset in a graph and A, B be the

sets of vertices and edges in W respectively.

For J(n, 1), since J(n, 1) is complete, we prove an even stronger assertion

that the result holds for all complete graphs. Let G be a complete graph

with |V (G)| = n and |A| = m. Denote the components of G − W by C

, C

and suppose that |V (C

)| = x. Then |V (C

)| = n − m − x, and |B| =

x(n − m − x) since B is a smallest edge-cut of G − A. κ

(G − A) = n − m − 1

since G is a complete graph. Hence n − m − 1 = x(n − m − x), that is

(x − 1)(x − (n − m − 1)) = 0. Therefore x = 1 or x = (n − m − 1), which

implies that |C

| = 1 or |C

| = 1. Without loss of generality, suppose that

| = 1 and v

is the vertex in C

. Clearly, W is a local cut at v

If k ≥ 2, then n ≥ 2k ≥ 4 for J(n, k). In the following, we ﬁrst prove that

http://www.paper.edu.cn

剩余10页未读，继续阅读

weixin_38665490

粉丝: 5
资源: 985

Johnson图的割集与哈密尔顿循环研究

基于net的超市管理系统源代码（完整前后端+sqlserver+说明文档+LW）.zip

LABVIEW程序实例-公式节点.zip

大米商城开源版damishop(适合外贸)

LABVIEW程序实例-通过全局变量接收数据.zip

LABVIEW程序实例-日历控件.zip

毕设和企业适用springboot人工智能客服系统类及旅游规划平台源码+论文+视频.zip

最新资源