Puneet Varma (Editor)

Dot product representation of a graph

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

A dot product representation of a simple graph is a method of representing a graph using vector spaces and the dot product from linear algebra. Every graph has a dot product representation.

Contents

Definition

Let G be a graph with vertex set V. Let F be a field, and f a function from V to Fk such that xy is an edge of G if and only if f(x)·f(y) ≥ t. This is the dot product representation of G. The number t is called the dot product threshold, and the smallest possible value of k is called the dot product dimension.

Properties

  • A threshold graph is a dot product graph with positive t and dot product dimension 1.
  • Every interval graph has dot product dimension at most 2.
  • Every planar graph has dot product dimension at most 4.

    • References

    Dot product representation of a graph Wikipedia
    (Text) CC BY-SA