Skip to main content
Article
Bipartite Dot Product Graphs
International Journal of Computer Mathematics: Computer Systems Theory
  • Sean Bailey, Texas A&M University
  • David E. Brown, Utah State University
Document Type
Article
Publisher
Taylor & Francis
Publication Date
6-23-2020
Disciplines
Abstract

Given a bipartite graph G = (X, Y, E), the bipartite dot product representation of G is a function f : X ∪Y → ℝk and a positive threshold t such that for any x ∈ X and y ∈ Y , xy ∈ E if and only if f(x) · f(y) ≥ t. The minimum k such that a bipartite dot product representation exists for G is the bipartite dot product dimension of G, denoted bdp(G). We will show that such representations exist for all bipartite graphs as well as give an upper bound for the bipartite dot product dimension of any graph. We will also characterize the bipartite graphs of bipartite dot product dimension 1 by their forbidden subgraphs.

Comments

This is an Accepted Manuscript of an article published by Taylor & Francis in International Journal of Computer Mathematics: Computer Systems Theory on June 23, 2020, available online: https://doi.org/10.1080/23799927.2020.1779820.

Citation Information
Sean Bailey & David Brown (2020) Bipartite dot product graphs, International Journal of Computer Mathematics: Computer Systems Theory, https://doi.org/10.1080/23799927.2020.1779820