主題
Search

單圖圖


單圖圖(或簡稱為“單圖”)是與每個具有該度序列的圖同構的圖。所有頂點數為四個或更少的圖都是單圖圖。

節點數為 n=1, 2, ... 的單圖圖的數量是 1, 2, 4, 11, 28, 72, 170, 407, 956, 2252 ... (OEIS A122423),其中連通圖的數量是 1, 1, 2, 6, 16, 42, 96, 234, 546, 1292, ... (OEIS A365548)。在所有節點數為 n 的連通圖中,具有不同度序列的連通圖的數量,對於 n=1, 2, ... 是 1, 1, 1, 2, 6, 17, 45, 99, 238, 549, 1296, ... (OEIS A309757)。

因此,在 5 個頂點上有 6 個非單圖圖,包括路徑圖 P_5P_2+C_3,它們共享度序列 (2,2,2,1,1)

如果圖 G 是單圖圖,則其圖補圖 G^_ 也是單圖圖 (Barrus et al. 2023)。

Kleitman (1975) 描述了一種用於線上性時間內識別單圖性的演算法。雖然單圖類沒有禁止的誘導子圖表徵,但可以透過分解來表徵它 (Barrus et al. 2023)。 特別是,圖 G 是單圖圖 當且僅當 其 Tyshkevich 分解的每個分量都是單圖圖 (Tyshkevich 2000, Barrus et al. 2023)。

唯一的正則單圖圖是完全圖 K_n空圖 K^__n梯子階圖 mK_2雞尾酒會圖 mK_2^_圈圖 C_5 (Johnson 1975, Koren 1976, Tyshkevich 2000)。


另請參閱

度序列, 圖序列, 頂點度

使用 探索

參考文獻

Barrus, M. D.; Trenk, A. N.; and Whitman, R. "The Hereditary Closure of the Unigraphs." 23 Aug 2023. https://arxiv.org/abs/2308.12190Johnson, R. H. "Simple Separable Graphs." Pacific J. Math. 56, 143-158, 1975.Kleitman, D. J. and Li, S.-Y. "A Note on Unigraphic Sequences." Stud. Appl. Math. 54, 283-287, 1975.Koren, M. "Pairs of Sequences with a Unique Realization by Bipartite Graphs." J. Combin. Th. Ser. B 21, 224-234, 1976.Koren, M. "Sequences with a Unique Realization by Simple Graphs." J. Combin. Th. Ser. B 21, 235-244, 1976.Li, S.-Y. R. "Graphic Sequences with Unique Realizations." J. Combin. Th. Ser. B 19, 42-68, 1975.Sloane, N. J. A. Sequences A122423, A309757, and A365548 in "The On-Line Encyclopedia of Integer Sequences."Tyshkevich, R. "The Canonical Decomposition of a Graph." Dokl. Akad. Nauk. BSSR 24, 677-679, 1980.Tyshkevich, R. "Decomposition of Graphical Sequences and Unigraphs." Disc. Math. 220, 201-238, 2000.

引用為

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

主題分類