主题
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 的无平方图则较为稀有。


参见

平方图, 图的环, 无三角形图

使用 Wolfram|Alpha 探索

参考文献

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."

在 Wolfram|Alpha 中被引用

无平方图

请引用为

Weisstein, Eric W. "无平方图。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/Square-FreeGraph.html

学科分类