非表示:
キーワード:
Mathematics, Combinatorics, math.CO,Computer Science, Discrete Mathematics, cs.DM
要旨:
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.
