Double graph

In the mathematical field of graph theory, the double graph of a simple graph $G$ is a graph derived from $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.^[1]

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

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

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

Properties

Double graphs have several notable properties that relate directly to the properties of the original graph $G$ .^[1]

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

Example

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

Applications

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.^[2]

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.^[2] These graph operations allow researchers to understand how topological properties of composite graphs relate to the properties of their simpler constituent graphs,^[2] which is particularly useful in chemical graph theory and mathematical chemistry applications.

Topological indices

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

Distance-based indices

For a connected graph $G$ with $n$ vertices:^[3]

Wiener index: $W(D[G])=4W(G)+2n$
Harary index: $H(D[G])=4H(G)+n/2$

Degree-based indices

For a graph $G$ :^[3]

First Zagreb index: $M_{1}(D[G])=8M_{1}(G)$
Second Zagreb index: $M_{2}(D[G])=16M_{2}(G)$
Randić index: $R(D[G])=2R(G)$
Atom-bond connectivity index: $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: $GA(D[G])=4GA(G)$

Combined degree-distance indices

For a connected graph $G$ with $m$ edges:^[3]

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

Eccentric connectivity index

For a connected graph $G$ with $n$ vertices, where $w(G)$ denotes the number of well-connected vertices:^[3]

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

For the lexicographic product and complete sum of graphs $G_{1}$ and $G_{2}$ :^[3]

$\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})$
$\xi ^{c}(D[G_{1}\boxplus G_{2}])=16|E(G_{1}\boxplus G_{2})|$

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

Strong double graph

While the double graph of a graph $G$ joins each vertex in one copy with the open neighborhood of the corresponding vertex in another copy, the strong double graph denoted $SD(G)$ joins each vertex with the closed neighborhood (neighbors plus the vertex itself) of the corresponding vertex.^[4]

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

Strong double graphs have several distinct properties:^[4]

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