A note on vector representation of graphs (Q1175424): Difference between revisions

Let \(G\) be a simple graph with vertices \(x_ 1,\dots,x_ n\). An orthogonal real (rational) representation of \(G\) is a list of non-zero vectors \(\bar x_ 1,\dots,\bar x_ n\) in \(\mathbb{R}^ d\) (\(\mathbb{Q}^ d\)) such that for all \(i\), \(j\) (\(1\leq i < j \leq n\)) the inner product \(\bar x_ i\bar x_ j\) is negative or zero according as the vertex \(x_ i\) is adjacent to \(x_ j\) or not. The least dimension \(d\) necessary for such a representation is denoted by \(d(G,\mathbb{R})\) or \(d(G,\mathbb{Q})\), respectively. \textit{T. D. Parsons} and \textit{T. Pisanski} [Discrete Math. 78, No. 1/2, 143-154 (1989; Zbl 0693.05058)] asked if \(d(G,\mathbb{R})=d(G,\mathbb{Q})\) for every graph \(G\). In the paper, this question is answered in the affirmative, and an explicit construction of an optimal representation for each graph is given.