论文标题
来自最小边缘盖的电感图尺寸
The Inductive Graph Dimension from The Minimum Edge Clique Cover
论文作者
论文摘要
在本文中，我们证明了归纳定义的图形维度在联接操作下具有简单的附加属性。两个简单图的联接的尺寸是组件图的尺寸的总和：$ \ mathrm {dim} \，（g_1+ g_2）= 1+ \ mathrm {dim} \，g_1+ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\ mathrm {dim}} \，g_2 $。我们使用此公式来得出从其最小边缘盖的任意有限简单图的电感尺寸的表达式。公式的推论是，任何任意有限的简单图形的最大集团都是订单$ n $的尺寸$ n-1 $。我们通过在简单图的电感尺寸上找到下层和上限，从其集团数字上找到下限和上限。
In this paper we prove that the inductively defined graph dimension has a simple additive property under the join operation. The dimension of the join of two simple graphs is one plus the sum of the dimensions of the component graphs: $\mathrm{dim}\, (G_1+ G_2) = 1 +\mathrm{dim}\, G_1+ \mathrm{dim}\, G_2$. We use this formula to derive an expression for the inductive dimension of an arbitrary finite simple graph from its minimum edge clique cover. A corollary of the formula is that any arbitrary finite simple graph whose maximal cliques are all of order $N$ has dimension $N-1$. We finish by finding lower and upper bounds on the inductive dimension of a simple graph in terms of its clique number.
