The Inductive Graph Dimension from The Minimum Edge Clique Cover

Publication date 6 March 2019

Abstract: In this paper we prove that the recursive (Knill) dimension of the join of two graphs has a simple formula in terms of the dimensions of the component graphs:

m a t h r m d i m, (G_{1} + G_{2}) = 1 + m a t h r m d i m, G_{1} + m a t h r m d i m, G_{2}

. We use this formula to derive an expression for the Knill dimension of a graph from its minimum clique cover. A corollary of the formula is that a graph made of the arbitrary union of complete graphs

K_{N}

of the same order

N

will have dimension

N - 1

. We finish by finding lower and upper bounds on the Knill dimension of a graph in terms of its clique number.

This page was built for publication: The Inductive Graph Dimension from The Minimum Edge Clique Cover

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6315172)