【作者】 马英红；

【Author】 MA Yinghong Department of Mathematics, Shandong University, Jinan 250100

【机构】 山东大学数学与系统科学学院；

【摘要】 布尔图是同构于n-维立方图的某个导出子图的图,布尔图的一个重要特征是可以用0-1序列标号来刻划顶点间的邻接关系,利用这一特性对图的顶点进行0-1序列标号,证明路、偶圈以及树都是布尔图,并给出了n-维立方图的最长布尔路和最大偶圈的长度的界的估计。同时证明了在n-维立方图中布尔路与布尔圈之间的内在联系,并以此给出了布尔路、布尔圈的长度估计的进一步改进。更多还原

【Abstract】 A graph is called a boolean graph if it is isomorphic to an induced subgraph of n-cube. An important property of the boolean graph is that the relationship among vertices could be described by 0, 1 binary. Paths, even cycles and trees were showed to be boolean graphs, and the bounds about the length of the longest path and the longest even cycle in the n-cube were given. At the same time, the relationship between the length of the longest path and the longest cycle was studied.更多还原