主題
Search

無平方圖


Square-FreeGraphs

無平方圖是不包含長度為 4 的圖的環的圖。一個簡單圖是無平方圖當且僅當

 c_4=1/8[Tr(A^4)-2m-2sum_(i!=j)a_(ij)^((2))]=0,

其中 A 是圖的鄰接矩陣Tr矩陣的跡m 是圖的邊數,並且 a_(ij)^((k)) 表示 i,j 元素的 A^k

n=1, 2, 3, ... 個節點上的無平方簡單圖的數量是 1, 2, 4, 8, 18, 44, 117, 351, ... (OEIS A006786),其中前幾個示例如上所示。

Square-FreeConnectedGraphs

n=1, 2, 3, ... 個節點上的無平方簡單連通圖的數量是 1, 1, 2, 3, 8, 19, 57, ... (OEIS A077269),其中前幾個示例如上所示。

圍長 >4 的圖自動是無平方圖,而圍長為 3 的無平方圖則較為稀有。


參見

平方圖, 圖的環, 無三角形圖

使用 探索

參考文獻

Harary, F. and Manvel, B. "On the Number of Cycles in a Graph." Mat. Časopis Sloven. Akad. Vied 21, 55-63, 1971.Sloane, N. J. A. 序列 A006786/M1149 和 A077269,出自 "The On-Line Encyclopedia of Integer Sequences."

在 中被引用

無平方圖

請引用為

Weisstein, Eric W. "無平方圖。" 來自 Web 資源。 https://mathworld.tw/Square-FreeGraph.html

學科分類