Double graph

In the mathematical field of graph theory, the double graph of a simple graph ${\displaystyle G}$ is a graph derived from ${\displaystyle G}$ by a specific construction. The concept and its elementary properties were detailed in a 2008 paper by Emanuele Munarini, Claudio Perelli Cippo, Andrea Scagliola, and Norma Zagaglia Salvi.¹

The double graph, denoted as ${\displaystyle {\mathcal {D}}[G]}$, of a simple graph ${\displaystyle G}$ is formally defined as the direct product of ${\displaystyle G}$ with the total graph ${\displaystyle T_{2}}$.¹ The graph ${\displaystyle T_{2}}$ is the complete graph ${\displaystyle K_{2}}$ with a loop added to each vertex.

An equivalent construction defines the double graph as the lexicographic product ${\displaystyle G\circ N_{2}}$, where ${\displaystyle N_{2}}$ is the null graph on two vertices (two vertices with no edges).¹

If a graph ${\displaystyle G}$ has ${\displaystyle n}$ vertices and ${\displaystyle m}$ edges, its double graph ${\displaystyle {\mathcal {D}}[G]}$ has ${\displaystyle 2n}$ vertices and ${\displaystyle 4m}$ edges.¹

Double graphs have several notable properties that relate directly to the properties of the original graph ${\displaystyle G}$.¹

• Adjacency matrix: If ${\displaystyle A}$ is the adjacency matrix of ${\displaystyle G}$, then the adjacency matrix of ${\displaystyle {\mathcal {D}}[G]}$ is the Kronecker product ${\displaystyle A\otimes J_{2}}$, where ${\displaystyle J_{2}}$ is the 2×2 matrix of ones.
• Regularity: A graph ${\displaystyle G}$ is ${\displaystyle k}$-regular if and only if its double ${\displaystyle {\mathcal {D}}[G]}$ is ${\displaystyle 2k}$-regular.
• Connectivity: ${\displaystyle G}$ is connected if and only if ${\displaystyle {\mathcal {D}}[G]}$ is connected. Furthermore, if ${\displaystyle G}$ is connected, then ${\displaystyle {\mathcal {D}}[G]}$ is Eulerian.
• Bipartite graph: ${\displaystyle G}$ is a bipartite graph if and only if ${\displaystyle {\mathcal {D}}[G]}$ is also bipartite.
• Spectrum: If the eigenvalues of ${\displaystyle G}$ are ${\displaystyle \lambda _{1},\dots ,\lambda _{n}}$, the spectrum of ${\displaystyle {\mathcal {D}}[G]}$ consists of the eigenvalues ${\displaystyle 2\lambda _{1},\dots ,2\lambda _{n}}$ and ${\displaystyle n}$ additional eigenvalues equal to zero.
• Chromatic number: The chromatic number of the double graph is the same as the original graph: ${\displaystyle \chi ({\mathcal {D}}[G])=\chi (G)}$.
• Isomorphism: Two graphs, ${\displaystyle G_{1}}$ and ${\displaystyle G_{2}}$, are isomorphic if and only if their doubles, ${\displaystyle {\mathcal {D}}[G_{1}]}$ and ${\displaystyle {\mathcal {D}}[G_{2}]}$, are isomorphic.

A notable example is the double of a complete graph ${\displaystyle K_{n}}$. The resulting graph, ${\displaystyle {\mathcal {D}}[K_{n}]}$, is the hyperoctahedral graph ${\displaystyle H_{n}}$.¹

Topological indices, including those computed for double graphs, have applications in chemistry and pharmaceutical research. These indices are used in the development of quantitative structure-activity relationships (QSARs) and quantitative structure-property relationships (QSPRs), where the biological activity or other properties of molecules are correlated with their chemical structure.²

The double graph construction, along with the related extended double cover and strong double graph constructions, has attracted attention in recent years due to its utility in studying various distance-based and degree-based topological indices.² These graph operations allow researchers to understand how topological properties of composite graphs relate to the properties of their simpler constituent graphs,² which is particularly useful in chemical graph theory and mathematical chemistry applications.

Various topological indices have been studied for double graphs.³ A topological index is a numerical quantity related to a graph that is invariant under graph automorphisms.

For a connected graph ${\displaystyle G}$ with ${\displaystyle n}$ vertices:³

• Wiener index: ${\displaystyle W(D[G])=4W(G)+2n}$
• Harary index: ${\displaystyle H(D[G])=4H(G)+n/2}$

For a graph ${\displaystyle G}$:³

• First Zagreb index: ${\displaystyle M_{1}(D[G])=8M_{1}(G)}$
• Second Zagreb index: ${\displaystyle M_{2}(D[G])=16M_{2}(G)}$
• Randić index: ${\displaystyle R(D[G])=2R(G)}$
• Atom-bond connectivity index: ${\displaystyle ABC(D[G])=2{\sqrt {2}}\sum _{e=uv\in E(G)}{\sqrt {\frac {d(u)+d(v)-1}{d(u)d(v)}}}}$
• Geometric-arithmetic index: ${\displaystyle GA(D[G])=4GA(G)}$

For a connected graph ${\displaystyle G}$ with ${\displaystyle m}$ edges:³

• Schultz index: ${\displaystyle S(D[G])=8S(G)+16m}$
• Modified Schultz index: ${\displaystyle S^{*}(D[G])=16S^{*}(G)+8M_{1}(G)}$
• Szeged index: ${\displaystyle Sz(D[G])=16Sz(G)}$
• Padmakar-Ivan index: ${\displaystyle PI(D[G])=8PI(G)}$
• Second geometric-arithmetic index: ${\displaystyle GA_{2}(D[G])=4GA_{2}(G)}$

For a connected graph ${\displaystyle G}$ with ${\displaystyle n}$ vertices, where ${\displaystyle w(G)}$ denotes the number of well-connected vertices:³

${\displaystyle \xi ^{c}(D[G])=4\xi ^{c}(G)+4w(G)(n-1)}$

For the lexicographic product and complete sum of graphs ${\displaystyle G_{1}}$ and ${\displaystyle G_{2}}$:³

• ${\displaystyle \xi ^{c}(D[G_{1}\circ G_{2}])=w(G_{1})(4n_{2}^{2}(n_{1}-1)+8m_{2})+4n_{2}^{2}\xi ^{c}(G_{1})+8m_{2}\zeta (G_{1})}$
• ${\displaystyle \xi ^{c}(D[G_{1}\boxplus G_{2}])=16|E(G_{1}\boxplus G_{2})|}$

where ${\displaystyle n_{i}=|V(G_{i})|}$, ${\displaystyle m_{i}=|E(G_{i})|}$, and ${\displaystyle \zeta (G_{1})}$ is the total eccentricity of ${\displaystyle G_{1}}$.

While the double graph of a graph ${\displaystyle G}$ joins each vertex in one copy with the open neighborhood of the corresponding vertex in another copy, the strong double graph denoted ${\displaystyle SD(G)}$ joins each vertex with the closed neighborhood (neighbors plus the vertex itself) of the corresponding vertex.⁴

The strong double graph can be expressed as the lexicographic product ${\displaystyle SD(G)=G\circ K_{2}}$, where ${\displaystyle K_{2}}$ is the complete graph on two vertices.⁴

Strong double graphs have several distinct properties:⁴

• Size: If ${\displaystyle G}$ has ${\displaystyle n}$ vertices and ${\displaystyle m}$ edges, then ${\displaystyle SD(G)}$ has ${\displaystyle 2n}$ vertices and ${\displaystyle 4m+n}$ edges.
• Bipartiteness: ${\displaystyle SD(G)}$ is bipartite if and only if ${\displaystyle G}$ is totally disconnected (i.e., ${\displaystyle G={\overline {K_{n}}}}$).
• Hamiltonian property: ${\displaystyle SD(G)}$ is Hamiltonian if and only if ${\displaystyle G}$ is connected with at least one vertex.
• Chromatic number: For any graph ${\displaystyle G}$ with at least one edge, ${\displaystyle 4\leq \chi (SD(G))\leq 2\Delta (G)+2}$, where ${\displaystyle \Delta (G)}$ is the maximum degree of ${\displaystyle G}$.
• Connectivity: The connectivity of ${\displaystyle SD(G)}$ is ${\displaystyle \kappa (SD(G))=2\kappa (G)}$.