主题
Search

图的粗糙度


G 的粗糙度 xi(G) 是给定图 G 中包含的最大数量的边不相交的非平面子图。因此,平面图 G 的粗糙度为 xi(G)=0

图的粗糙度是其 的粗糙度之和 (Beineke and Chartrand 1968)。

完全图 K_n 的粗糙度对于 n 的大多数值是已知的,除了 n=13n 可被 3 整除且大于或等于 18,以及 n 形式为 9k+7 的情况。对于所有这些情况,已知值在 1 以内 (Guy and Beineke 1968; Harary 1994, pp. 121-122)。

完全二分图 K_(m,n) 的粗糙度对于满足某些条件的 m,n 值是已知的 (Beineke and Guy 1969; Harary 1994, pp. 121-122)。


另请参阅

图的厚度, 非平面图

使用 Wolfram|Alpha 探索

参考文献

Beineke, L. W. and Chartrand, G. "The Coarseness of a Graph." Compos. Math. 19, 290-298, 1968.Beineke, L. W. and Guy, R. K. "The Coarseness of the Complete Bipartite Graph." Canad. J. Math. 21, 1086-1096, 1969.Guy, R. and Beineke, L. "'THe Coarseness of the Complete Graph." Canad. J. Math. 20, 888-894, 1968.Harary, F. "Covering and Packing in Graphs, I." Ann. New York Acad. Sci. 175, 198-205, 1970.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, pp. 121-122, 1994.Harary, F. and Palmer, E. M. Graphical Enumeration. New York: Academic Press, p. 225, 1973.Harary, F. and Palmer, E. M. "A Survey of Graph Enumeration Problems." In A Survey of Combinatorial Theory (Ed. J. N. Srivastava). Amsterdam: North-Holland, pp. 259-275, 1973.Kainen, P. C. "Thickness and Coarseness of Graphs." Abh. Math. Semin. Univ. Hamburg 39, 88-95, 1973.

在 Wolfram|Alpha 中引用

图的粗糙度

引用为

Weisstein, Eric W. "图的粗糙度。" 来自 MathWorld—— Wolfram 网络资源。 https://mathworld.net.cn/GraphCoarseness.html

主题分类