Bipartite dot product graphs. Issue 3 (2nd July 2020)

• Record Type: Journal Article
• Authors: Bailey, Sean; Brown, David
• Is Part Of: International journal of computer mathematics. Volume 5:Issue 3(2020)
• Page Start: 148
• Page End: 158
• Publication Date: 2020-07-02
• Subjects: Graph theory -- dot product graphs -- bipartite graphs -- graph representations -- subgraph categorization; 05C62 -- 05C75; Computer systems -- Periodicals; Computer systems; Periodicals; 004
• DOI: 10.1080/23799927.2020.1779820
• Languages: English
• ISSNs: 2379-9927

Abstract

Abstract : Given a bipartite graph G = ( X, Y, E ), the bipartite dot product representation of G is a function f : X ∪ Y → R k and a positive threshold t such that for any x ∈ X and y ∈ Y, x y ∈ 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 b d p ( 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.