主題
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 圖, 對稱圖

使用 探索

參考文獻

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.

在 中被引用

Bouwer 圖

請引用為

Weisstein, Eric W. "Bouwer 圖。" 來自 Web 資源。 https://mathworld.tw/BouwerGraph.html

主題分類