Professor Matthew Johnson matthew.johnson2@durham.ac.uk
Head Of Department
What graphs are 2-dot product graphs?
Johnson, M.; van Leeuwen, E.J.; Paulusma, D.
Authors
E.J. van Leeuwen
Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor
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). What graphs are 2-dot product graphs?. . https://doi.org/10.1016/j.endm.2015.06.095
Conference Name | European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2015), |
---|---|
Conference Location | Bergen, Norway |
Publication Date | Nov 12, 2015 |
Deposit Date | Aug 12, 2015 |
Publicly Available Date | Mar 29, 2024 |
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. |
Files
Accepted Conference Proceeding
(232 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by-nc-nd/4.0/
Copyright Statement
© 2015 This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/
You might also like
Independent transversals versus transversals
(2019)
Conference Proceeding
Connected vertex cover for (sP1+P5)-free graphs
(2019)
Journal Article
Filling the complexity gaps for colouring planar and bounded degree graphs
(2019)
Journal Article
Finding a small number of colourful components
(2019)
Conference Proceeding
Clique-width for hereditary graph classes
(2019)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search