What graphs are 2-dot product graphs?

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

Abstract

From a set of d-dimensional vectors for some integer d ≥ 1, we obtain a d-dot product graph by letting each vector au correspond to a vertex u and by adding an edge between two vertices u and v if and only if their dot product au · av ≥ t, for some fixed, positive threshold t. Dot product graphs can be used to model social networks. 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.

Citation

Johnson, M., van Leeuwen, E., & Paulusma, D. (2015, November). What graphs are 2-dot product graphs?. Presented at European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2015),, Bergen, Norway

• Presentation Conference Type: Conference Paper (published)
• Conference Name: European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2015),
• Publication Date: Nov 12, 2015
• Deposit Date: Aug 12, 2015
• Publicly Available Date: Nov 12, 2016
• Volume: 49
• Pages: 705-711
• Series Title: Electronic Notes in Discrete Mathematics
• Series ISSN: 1571-0653
• DOI: https://doi.org/10.1016/j.endm.2015.06.095
• Keywords: Dot product graphs, Social networks, Graph classes.
• Public URL: https://durham-repository.worktribe.com/output/1153656