English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Paper

What Graphs are 2-Dot Product Graphs?

MPS-Authors
/persons/resource/persons98374

van Leeuwen,  Erik Jan
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (public)

arXiv:1511.05009.pdf
(Preprint), 137KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Johnson, M., Paulusma, D., & van Leeuwen, E. J. (2015). What Graphs are 2-Dot Product Graphs? Retrieved from http://arxiv.org/abs/1511.05009.


Cite as: http://hdl.handle.net/11858/00-001M-0000-002C-5393-3
Abstract
Let $d \geq 1$ be an integer. From a set of $d$-dimensional vectors, we obtain a $d$-dot product graph by letting each vector ${\bf 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 ${\bf a}^{u} \cdot {\bf a}^{v} \geq 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\geq 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.