Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Physical Sciences and Mathematics
The Knill Graph Dimension From The Minimum Clique Cover, Kassahun Betre, Evatt Salinger
The Knill Graph Dimension From The Minimum Clique Cover, Kassahun Betre, Evatt Salinger
Faculty Publications
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: dim(G1+G2)=1+dimG1+dimG2. 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 KN 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.