On orthogonal representations of graphs
type: Item
instance of: scholarly article
title: On orthogonal representations of graphs
zbMATH Open document ID: 0962.05042
DOI: 10.1016/S0012-365X(00)00168-0
author: Vadim Lozin
author: V. E. Alekseev
published in: Discrete Mathematics
publication date: 2001-06-04T00:00:00Z
review text: A simple graph on the vertex set \(\{ 1,2, \dots ,n \}\) can be represented by \(d\)-tuples \(x_1, \ldots ,x_n\) with entries from a field \(F\) where \(x_ix_j=x_i^1x_j^1 + x_i^2x_j^2 + \cdots + x_i^dx_j^d\) is 0 if and only if \(i\) and \(j\) are nonadjacent in \(G\). For such representations, the dimension is at most \(n-1\) for general fields, and at most \(n-2\) for fields of characteristic 2 and graphs other than the \(n\)-path.
reviewed by: Norman F. Quimpo
Mathematics Subject Classification ID: 05C62
zbMATH DE Number: 1565953
zbMATH Keywords: vector representation of a graph
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1565953