主题
Search

Bouwer 图

DOWNLOAD Mathematica Notebook下载 Wolfram 笔记本

Bouwer 图，这是一个首次在此处提出的术语，是一系列正则图，其中包括对称但不弧传递的成员。Alspach 等人 (1994) 将此类图称为 1/2-传递图。

Bouwer 对此类图的一般构造定义了一个图 B(N,m,n)，其中 N>=2 且 m,n>=2，使得 2^m=1 (mod n)。此图的顶点集被定义为笛卡尔积

Z_m×Z_n×...×Z_n_()_(N-1),

其中 Z_i 表示模 i 的整数环，边集由 边集 N 元组对组成

{(i,a_2,a_3,...,a_N),(i+1,b_2,b_3,...,b_N)}

对于 i=1, ..., m（模 m 加法）和 a_i,b_i=2, ..., N，使得对于所有 r=2, 3, ..., N，b_r=a_r，或者恰好存在一个 s in {2,3,...,N}，使得 b_s!=a_s，在这种情况下，它被视为 b_s=a_s+2^i (mod n)。

根据构造，这些图是对称的，并且包括以下被命名的弧传递图。

(N,m,n)图
(2,2,3)圈图 C_6
(2,3,7)广义六边形 GH(2,1)
(2,4,3)循环图 Ci_(12)(1,5)
(2,4,5)525-Haar 图
(2,6,3)四次顶点传递图 Qt66
(3,2,3)帕普斯图

然而，这类图也包括对称但非边传递的成员。Tutte (1966) 最先考虑了这类图，他没有构造任何图，但表明如果存在，任何这样的图都必须是偶数度的正则图。因此，Bouwer (1970) 给出了第一个例子，他表明 B(N,6,9) 对于所有整数 N>=2 都是连通的 2N-正则对称非弧传递图。这类图有 6·9^N 个顶点，对于 N=2, 3, ...，给出的图的顶点计数为 54、486、4374、39366、354294、...

BouwerGraph269

这种图的最小 ((N=2)) 示例是在 54 个顶点上的四次对称图，如上图在几个嵌入中所示。这个图可以从顶点集 {(alpha,beta)|alpha in Z_6,beta in Z_9} 中简洁地描述和构造，其中 (alpha,beta) 连接到 (alpha+/-1,beta)、(alpha+1,beta+2^alpha) 和 (alpha-1,beta-2^(alpha-1)) (Holt 1981)。

Dolye (1976) 和 Holt (1981) 随后发现了较小的对称非弧传递图，现在称为 Doyle 图，可以通过收缩 Bouwer 的 54 顶点图的直径相对的顶点对来获得 (Doyle 1998)。

下表 (Weisstein，2010 年 11 月 17 日) 给出了使用 Brouwer 方法构造的小型对称非弧传递图的部分列表，其中 v 是顶点计数。这些图在 Wolfram 语言中实现为GraphData[{"Bouwer", {N, m, n}}].

vB(N,m,n)
54B(2,6,9)
60B(2,4,15)
63B(2,9,7)
84B(2,12,7)
100B(3,4,5)

另请参阅

弧传递图, Doyle 图, 对称图

使用 Wolfram|Alpha 探索

参考文献

Alspach, B.; Marušič, Dragan; and Nowitz, L. (1994), "构造 1/2-传递图。" J. Austral. Math. Soc. 56, 391-402, 1994.Bouwer, I. Z. "顶点和边传递但非 1-传递图。" Canad. Math. Bull. 13, 231-237, 1970.Doyle, P. G. 关于传递图。 Senior Thesis. Cambridge, MA, Harvard College, April 1976.Doyle, P. "一个 27 顶点图，它是顶点传递和边传递的，但不是 L-传递的。" October 1998. http://arxiv.org/abs/math/0703861.Holt, D. F. "一个边传递但非弧传递的图。" J. Graph Th. 5, 201-204, 1981.Tutte, W. T. 图的连通性。 Toronto, CA: University of Toronto Press, 1966.

在 Wolfram|Alpha 中被引用

Bouwer 图

请引用为

Weisstein, Eric W. "Bouwer 图。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/BouwerGraph.html

主题分类