The Exponents of Double Vertex Graphs

Abstract

Let $G$ be a simple graph. The double vertex graph $U_2(G)$ of $G$ is the graph whose vertex set consists of all $2$-subsets of $V(G)$ such that two distinct vertices $\{x,y\}$ and $\{u,v\}$ are adjacent if and only if $|\{x,y\}\cap \{u,v\}|=1$ and if $x=u$, then $y$ and $v$ are adjacent in $G$. In this paper, we consider the exponents and primitivity relationships between a simple graph and its double vertex graph. A sharp upper bound on exponents of double vertex graphs of primitive simple graphs and the characterization of extremal graphs are obtained.