Double graph

Short description: Graph operation in graph theory

The double of the graph C₈

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.

Definition

The double graph, denoted as ${𝒟}[G]$, of a simple graph $G$ is formally defined as the direct product of $G$ with the total graph $T_2$. 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).

If a graph $G$ has $n$ vertices and $m$ edges, its double graph ${𝒟}[G]$ has $2n$ vertices and $4m$ edges.

Properties

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

• Adjacency matrix: If $A$ is the adjacency matrix of $G$, then the adjacency matrix of ${𝒟}[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 ${𝒟}[G]$ is $2k$-regular.
• Connectivity: $G$ is connected if and only if ${𝒟}[G]$ is connected. Furthermore, if $G$ is connected, then ${𝒟}[G]$ is Eulerian.
• Bipartite graph: $G$ is a bipartite graph if and only if ${𝒟}[G]$ is also bipartite.
• Spectrum: If the eigenvalues of $G$ are ${\lambda }_1,\dots ,{\lambda }_n$, the spectrum of ${𝒟}[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 ({𝒟}[G])=\chi (G)$.
• Isomorphism: Two graphs, $G_1$ and $G_2$, are isomorphic if and only if their doubles, ${𝒟}[G_1]$ and ${𝒟}[G_2]$, are isomorphic.

Example

A notable example is the double of a complete graph $K_n$. The resulting graph, ${𝒟}[K_n]$, is the hyperoctahedral graph $H_n$.

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.

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.

Topological indices

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.

Distance-based indices

For a connected graph $G$ with $n$ vertices:

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

Degree-based indices

For a graph $G$:

• 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:

• 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: $G{A}_2(D[G])=4G{A}_2(G)$

Eccentric connectivity index

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

${\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$:

• ${\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⊞G_2])=16|E(G_1⊞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.

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.

Strong double graphs have several distinct properties:

• 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\le \chi (SD(G))\le 2\mathrm{\Delta }(G)+2$, where $\mathrm{\Delta }(G)$ is the maximum degree of $G$.
• Connectivity: The connectivity of $SD(G)$ is $\kappa (SD(G))=2\kappa (G)$.