What graphs are 2-dot product graphs?

DOI10.1016/J.ENDM.2015.06.095zbMATH Open1346.05246arXiv1511.05009OpenAlexW2963645630MaRDI QIDQ322356FDOQ322356

Authors: Matthew Johnson, Erik Jan van Leeuwen, Daniël Paulusma 

Publication date: 14 October 2016

Abstract: Let $dgeq1$ be an integer. From a set of $d$-dimensional vectors, we obtain a $d$-dpg by letting each vector $v{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 $v{a}^{u}cdotv{a}^{v}geqt$, 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 $dgeq2$. 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 including a number of well-known classes of intersection graphs.

Full work available at URL: https://arxiv.org/abs/1511.05009

Recommendations

• Dot product representations of graphs
• Random Dot Product Graph Models for Social Networks
• Dot product representations of planar graphs
• Dot product representations of planar graphs
• Algorithms to measure diversity and clustering in social networks through dot product graphs

zbMATH Keywords

social networksgraph classesdot product graphs

Mathematics Subject Classification ID

Social networks; opinion dynamics (91D30) Graph operations (line graphs, products, etc.) (05C76)

Cites Work

• Kronecker graphs: an approach to modeling networks
• Random Dot Product Graph Models for Social Networks
• Latent Space Approaches to Social Network Analysis
• Title not available (Why is that?)
• Dot product representations of graphs
• Dot product dimensions of graphs
• Directed Random Dot Product Graphs
• Sphere and dot product representations of graphs
• Multiplicative attribute graph model of real-world networks
• Modeling graphs using dot product representations
• Dot product representations of planar graphs

Cited In (2)

• What Graphs are 2-Dot Product Graphs?
• Dot product dimension of unicyclic graphs

Uses Software

• KronFit

This page was built for publication: What graphs are 2-dot product graphs?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q322356)