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.