What graphs are 2-dot product graphs?

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

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