On the contact dimensions of graphs (Q579284): Difference between revisions

Every simple graph \(G=(V,E)\) can be represented by a family of equal nonoverlapping spheres \(\{S_ v:\) \(v\in V\}\) in a Euclidean space \(R^ n\) in such a way that uv\(\in E\) if and only if \(S_ u\) and \(S_ v\) touch each other. The smallest dimension n needed to represent G in such a way is called the contact dimension of G and it is denoted by cd(G). We prove that (1) \(cd(T)<(7.3)\) log\(| T|\) for every tree T, and \[ (2)\quad m-1+\frac{n}{2}(1-\frac{n}{2\pi m}(\sqrt{\frac{n+4\pi m}{n}}- 1))<cd(K_ m+E_ n)\leq m-1+\lceil \frac{n}{2}\rceil, \] where \(K_ m+E_ n\) is the join of the complete graph of order m and the empty graph of order n. For the complete bipartite graph \(K_{n,n}\) this implies \((1.286)n-1<cd(K_{n,n})<(1.5)n\).