Skip to main content

Research Repository

Advanced Search

What graphs are 2-dot product graphs?

Johnson, M.; Paulusma, D.; van Leeuwen, E.J.

What graphs are 2-dot product graphs? Thumbnail


Authors

E.J. van Leeuwen



Abstract

Let d ≥ 1 be an integer. From a set of d-dimensional vectors, we obtain a d-dot product graph by letting each vector a u correspond to a vertex u and by adding an edge between two vertices u and v if and only if their dot product a u · a v ≥ t, for some fixed, positive threshold t. Dot product graphs can be used to model social networks. Recognizing a d-dot product graph is known to be NP-hard for all fixed d ≥ 2. To understand the position of d-dot product graphs in the landscape of graph classes, we consider the case d = 2, and investigate how 2-dot product graphs relate to a number of other known graph classes including a number of well-known classes of intersection graphs.

Citation

Johnson, M., Paulusma, D., & van Leeuwen, E. (2021). What graphs are 2-dot product graphs?. International Journal of Computational Geometry and Applications, 31(01), 1-16. https://doi.org/10.1142/s0218195921500011

Journal Article Type Article
Acceptance Date Jun 26, 2021
Online Publication Date Sep 10, 2021
Publication Date 2021-03
Deposit Date Aug 23, 2021
Publicly Available Date Sep 10, 2022
Journal International Journal of Computational Geometry and Applications
Print ISSN 0218-1959
Electronic ISSN 1793-6357
Publisher World Scientific Publishing
Peer Reviewed Peer Reviewed
Volume 31
Issue 01
Pages 1-16
DOI https://doi.org/10.1142/s0218195921500011
Public URL https://durham-repository.worktribe.com/output/1243268

Files





You might also like



Downloadable Citations