We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham University

Computer Science


Publication details for Professor Matthew Johnson

Johnson, M., van Leeuwen, E.J. & Paulusma, D. (2015), What graphs are 2-dot product graphs?, Electronic Notes in Discrete Mathematics 49: The Eight European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2015. Bergen, Norway, Elsevier, Bergen, 705-711.

Author(s) from Durham


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.