Double graph

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

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

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

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

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

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

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

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.

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.

For a connected graph G {\displaystyle G} with n {\displaystyle n} vertices:^[3]

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

For a graph G {\displaystyle G} :^[3]

• First Zagreb index: M 1 ( D [ G ] ) = 8 M 1 ( G ) {\displaystyle M_{1}(D[G])=8M_{1}(G)}
• Second Zagreb index: M 2 ( D [ G ] ) = 16 M 2 ( G ) {\displaystyle M_{2}(D[G])=16M_{2}(G)}
• Randić index: R ( D [ G ] ) = 2 R ( G ) {\displaystyle R(D[G])=2R(G)}
• Atom-bond connectivity index: A B C ( D [ G ] ) = 2 2 ∑ e = u v ∈ E ( G ) d ( u ) + d ( v ) − 1 d ( u ) d ( v ) {\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: G A ( D [ G ] ) = 4 G A ( G ) {\displaystyle GA(D[G])=4GA(G)}

For a connected graph G {\displaystyle G} with m {\displaystyle m} edges:^[3]

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

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

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

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

• ξ c ( D [ G 1 ∘ G 2 ] ) = w ( G 1 ) ( 4 n 2 2 ( n 1 − 1 ) + 8 m 2 ) + 4 n 2 2 ξ c ( G 1 ) + 8 m 2 ζ ( G 1 ) {\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})}
• ξ c ( D [ G 1 ⊞ G 2 ] ) = 16 | E ( G 1 ⊞ G 2 ) | {\displaystyle \xi ^{c}(D[G_{1}\boxplus G_{2}])=16|E(G_{1}\boxplus G_{2})|}

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

While the double graph of a graph G {\displaystyle G} joins each vertex in one copy with the open neighborhood of the corresponding vertex in another copy, the strong double graph denoted S D ( G ) {\displaystyle 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 S D ( G ) = G ∘ K 2 {\displaystyle SD(G)=G\circ K_{2}} , where K 2 {\displaystyle K_{2}} is the complete graph on two vertices.^[4]

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

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