The Inductive Graph Dimension from The Minimum Edge Clique Cover

Abstract

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: $\dim (G_1+G_2)=1+\dim G_1+\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.

arXiv admin note: substantial text overlap with arXiv:1903.02523 author note: this version was meant to be a replacement of arXiv:1903.02523, but due to submission mistake it appeared as a new submission