主題
Search

道爾圖


DoyleGraph

道爾圖,有時也稱為霍爾特圖(Marušič等人 2005),是上述幾個嵌入中所示的 27 個節點的四次對稱圖。它之所以引人注目,是因為它是一個小圖,它是對稱的,但不是弧傳遞的。換句話說,道爾圖的任何邊都可以對映到任何其他邊,但只有兩種可能的方式中的一種。

根據 Alspach等人 (1994) 的說法,將頂點傳遞邊傳遞圖但不是弧傳遞圖的圖稱為“1/2-傳遞圖”。道爾圖實際上是唯一的最小 1/2-傳遞圖(Alspach等人 1994)。請注意,雖然 Holt (1981) 提到一位審稿人告知他 Kornya 發現了另一個具有 27 個頂點的例子,但道爾圖實際上是唯一的具有 27 個頂點且度數為 4 的 l/2-傳遞圖(Alspach等人 1994)。

Tutte (1966) 首先考慮了此類圖,他表明任何 1/2-傳遞圖必須是偶數度的正則圖。Bouwer (1970) 給出了第一個例子,他為所有整數2n正則對稱弧非傳遞連通圖給出了構造性證明n>=2。最小的此類鮑威爾圖有 54 個頂點,並且是四次圖

Dolye (1976) 和隨後的 Holt (1981) 發現了現在稱為道爾圖的圖。該圖可以透過收縮 Bouwer 的 54 頂點圖的直徑相對的頂點對來獲得(Doyle 1998)。它也是(3,3)-漢明圖的子圖。上面說明了幾個嵌入,其中第一個歸功於 Doyle (1998),最後一個歸功於 Marušič等人 (2005)。

它在 Wolfram 語言中實現為GraphData["DoyleGraph"].

該圖可以從頂點集{(alpha,beta)|alpha in Z_9,beta in Z_3}簡潔地描述和構造,其中(alpha,beta)連線到(4alpha+/-1,beta-1)(7alpha+/-7,beta+1) (Holt 1981)。

DoyleGraphUnitDistance

道爾圖是一個單位距離圖。上面說明了許多單位距離嵌入,包括 E. Gerbracht 的邊-頂點退化嵌入(私人通訊,2009 年 12 月 27 日)和 E. Weisstein(2023 年 10 月 26 日),以及 J. Tan 的一個美觀(且唯一)最大對稱嵌入(私人通訊,2021 年 10 月 16 日)。

DoyleGraphLCF

道爾圖有兩個不同的 9 階 LCF 符號和十六個 3 階 LCF 符號,如上所示,以及 1818 個 1 階 LCF 符號。

下表總結了它的一些屬性,其中alpha, beta, 和 gammax^3-6x+2的(實)根,按從小到大排序。


另請參閱

弧傳遞圖, 鮑威爾圖, 四次圖, 四次對稱圖

使用 探索

參考文獻

Alspach, B.; Marušič, Dragan; and Nowitz, L. (1994), "Constructing Graphs which are 1/2-Transitive." J. Austral. Math. Soc. 56, 391-402, 1994.Bouwer, Z. "Vertex and Edge Transitive, But Not 1-Transitive Graphs." Canad. Math. Bull. 13, 231-237, 1970.Doyle, P. G. On Transitive Graphs. Senior Thesis. Cambridge, MA, Harvard College, April 1976.Doyle, P. "A 27-Vertex Graph That Is Vertex-Transitive and Edge-Transitive But Not L-Transitive." October 1998. http://arxiv.org/abs/math/0703861.Godsil, C. and Royle, G. Algebraic Graph Theory. New York: Springer-Verlag, p. 37, 2001.Holt, D. F. "A Graph Which Is Edge Transitive But Not Arc Transitive." J. Graph Th. 5, 201-204, 1981.Marušič, D.; Pisanski, T.; and Wilson, S. "The Genus of the Gray Graph is 7." Europ. J. Combin. 26, 377-385, 2005.Pisanski, T. and Randić, M. "Bridges between Geometry and Graph Theory." In Geometry at Work: A Collection of Papers Showing Applications of Geometry (Ed. C. A. Gorini). Washington, DC: Math. Assoc. Amer., pp. 174-194, 2000.Tan, J. "Of Christmas Lights: the Nine Colourings of the Holt Graph." Dec. 16, 2021. https://community.wolfram.com/groups/-/m/t/2426803.Tutte, W. T. Connectivity in Graphs. Toronto, CA: University of Toronto Press, 1966.

請引用為

Weisstein, Eric W. "道爾圖。" 來自 Web 資源。 https://mathworld.tw/DoyleGraph.html

學科分類