# Double graph

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Double_graph
> Markdown URL: https://mediated.wiki/source/Double_graph.md
> Source: https://en.wikipedia.org/wiki/Double_graph
> Source revision: 1327644578
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{short description|Graph operation in graph theory}}
[[File:Double graph of C 5.svg|thumb|upright=1.2|The double of the graph [{{mvar|C{{sub|8}}}}](/source/cycle_graph)]]

In the mathematical field of [graph theory](/source/graph_theory), the '''double graph''' of a [simple graph](/source/simple_graph) <math>G</math> is a graph derived from <math>G</math> 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.<ref name="Munarini2008">{{cite journal |last1=Munarini |first1=Emanuele |last2=Cippo |first2=Claudio Perelli |last3=Scagliola |first3=Andrea |last4=Salvi |first4=Norma Zagaglia |title=Double graphs |journal=Discrete Mathematics |volume=308 |issue=2 |pages=242–254 |year=2008 |doi=10.1016/j.disc.2006.11.038}}</ref>

== Definition ==
The double graph, denoted as <math>\mathcal{D}[G]</math>, of a simple graph <math>G</math> is formally defined as the [direct product](/source/tensor_product_of_graphs) of <math>G</math> with the [total graph](/source/total_graph) <math>T_2</math>.<ref name="Munarini2008" /> The graph <math>T_2</math> is the [complete graph](/source/complete_graph) <math>K_2</math> with a [loop](/source/loop_(graph_theory)) added to each vertex.

An equivalent construction defines the double graph as the [lexicographic product](/source/lexicographic_product_of_graphs) <math>G \circ N_2</math>, where <math>N_2</math> is the [null graph](/source/null_graph) on two vertices (two vertices with no edges).<ref name="Munarini2008" />

If a graph <math>G</math> has <math>n</math> vertices and <math>m</math> edges, its double graph <math>\mathcal{D}[G]</math> has <math>2n</math> vertices and <math>4m</math> edges.<ref name="Munarini2008" />

== Properties ==
Double graphs have several notable properties that relate directly to the properties of the original graph <math>G</math>.<ref name="Munarini2008" />

*  [Adjacency matrix](/source/Adjacency_matrix): If <math>A</math> is the adjacency matrix of <math>G</math>, then the adjacency matrix of <math>\mathcal{D}[G]</math> is the [Kronecker product](/source/Kronecker_product) <math>A \otimes J_2</math>, where <math>J_2</math> is the 2×2 [matrix of ones](/source/matrix_of_ones).
*  [Regularity](/source/Regular_graph): A graph <math>G</math> is <math>k</math>-regular if and only if its double <math>\mathcal{D}[G]</math> is <math>2k</math>-regular.
*  [Connectivity](/source/Connectivity_(graph_theory)): <math>G</math> is connected if and only if <math>\mathcal{D}[G]</math> is connected. Furthermore, if <math>G</math> is connected, then <math>\mathcal{D}[G]</math> is [Eulerian](/source/Eulerian_path).
*  [Bipartite graph](/source/Bipartite_graph): <math>G</math> is a bipartite graph if and only if <math>\mathcal{D}[G]</math> is also bipartite.
*  [Spectrum](/source/Spectral_graph_theory): If the [eigenvalues](/source/eigenvalues) of <math>G</math> are <math>\lambda_1, \dots, \lambda_n</math>, the spectrum of <math>\mathcal{D}[G]</math> consists of the eigenvalues <math>2\lambda_1, \dots, 2\lambda_n</math> and <math>n</math> additional eigenvalues equal to zero.
*  [Chromatic number](/source/Graph_coloring): The chromatic number of the double graph is the same as the original graph: <math>\chi(\mathcal{D}[G]) = \chi(G)</math>.
*  [Isomorphism](/source/Graph_isomorphism): Two graphs, <math>G_1</math> and <math>G_2</math>, are isomorphic if and only if their doubles, <math>\mathcal{D}[G_1]</math> and <math>\mathcal{D}[G_2]</math>, are isomorphic.

== Example ==
A notable example is the double of a [complete graph](/source/complete_graph) <math>K_n</math>. The resulting graph, <math>\mathcal{D}[K_n]</math>, is the hyperoctahedral graph <math>H_n</math>.<ref name="Munarini2008" />

== 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)](/source/QSAR) and quantitative structure-property relationships (QSPRs), where the biological activity or other properties of molecules are correlated with their chemical structure.<ref name="Azari2022">{{cite journal |last=Azari |first=Mahdieh |title=Three Constructions on Graphs and Distance-Based Invariants |journal=Mathematics Interdisciplinary Research |volume=7 |pages=89–103 |year=2022 |url=https://mir.kashanu.ac.ir/article_111491_0310d92d0ad3bbb8511e3db4dffce768.pdf |doi=10.22052/MIR.2021.242881.1292 |doi-access=free}}</ref>

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.<ref name="Azari2022"/> These graph operations allow researchers to understand how topological properties of composite graphs relate to the properties of their simpler constituent graphs,<ref name="Azari2022"/> which is particularly useful in [chemical graph theory](/source/chemical_graph_theory) and [mathematical chemistry](/source/mathematical_chemistry) applications.

== Topological indices ==
Various [topological indices](/source/topological_index) have been studied for double graphs.<ref name="gm23">{{cite journal |last1=Ghasemi |first1=Mehdi |last2=Madanshekaf |first2=Ali |title=On the Topological Indices on Double Graphs |journal=Caspian Journal of Mathematical Sciences |volume=12 |issue=2 |pages=423–439 |date=27 September 2023 |doi=10.22080/CJMS.2023.25624.1660 |doi-access=free}}</ref> A topological index is a numerical quantity related to a graph that is invariant under graph automorphisms.

=== Distance-based indices ===
For a connected graph <math>G</math> with <math>n</math> vertices:<ref name="gm23"/>

* [Wiener index](/source/Wiener_index): <math>W(D[G]) = 4W(G) + 2n</math>
* [Harary index](/source/Harary_index): <math>H(D[G]) = 4H(G) + n/2</math>

=== Degree-based indices ===
For a graph <math>G</math>:<ref name="gm23"/>

* First [Zagreb index](/source/Zagreb_index): <math>M_1(D[G]) = 8M_1(G)</math>
* Second Zagreb index: <math>M_2(D[G]) = 16M_2(G)</math>
* [Randić index](/source/Randi%C4%87_index): <math>R(D[G]) = 2R(G)</math>
* Atom-bond connectivity index: <math>ABC(D[G]) = 2\sqrt{2} \sum_{e=uv \in E(G)} \sqrt{\frac{d(u) + d(v) - 1}{d(u)d(v)}}</math>
* Geometric-arithmetic index: <math>GA(D[G]) = 4GA(G)</math>

=== Combined degree-distance indices ===
For a connected graph <math>G</math> with <math>m</math> edges:<ref name="gm23"/>

* [Schultz index](/source/Schultz_index): <math>S(D[G]) = 8S(G) + 16m</math>
* Modified Schultz index: <math>S^*(D[G]) = 16S^*(G) + 8M_1(G)</math>
* [Szeged index](/source/Szeged_index): <math>Sz(D[G]) = 16Sz(G)</math>
* [Padmakar-Ivan index](/source/Padmakar-Ivan_index): <math>PI(D[G]) = 8PI(G)</math>
* Second geometric-arithmetic index: <math>GA_2(D[G]) = 4GA_2(G)</math>

=== Eccentric connectivity index ===
For a connected graph <math>G</math> with <math>n</math> vertices, where <math>w(G)</math> denotes the number of [well-connected vertices](/source/Glossary_of_graph_theory):<ref name="gm23"/>

:<math>\xi^c(D[G]) = 4\xi^c(G) + 4w(G)(n - 1)</math>

For the [lexicographic product](/source/lexicographic_product_of_graphs) and [complete sum](/source/complete_sum) of graphs <math>G_1</math> and <math>G_2</math>:<ref name="gm23"/>

* <math>\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)</math>
* <math>\xi^c(D[G_1 \boxplus G_2]) = 16|E(G_1 \boxplus G_2)|</math>

where <math>n_i = |V(G_i)|</math>, <math>m_i = |E(G_i)|</math>, and <math>\zeta(G_1)</math> is the total eccentricity of <math>G_1</math>.

== Strong double graph ==
While the double graph of a graph <math>G</math> joins each vertex in one copy with the ''open [neighborhood](/source/Neighbourhood_(graph_theory))'' of the corresponding vertex in another copy, the '''strong double graph''' denoted <math>SD(G)</math> joins each vertex with the ''closed neighborhood'' (neighbors plus the vertex itself) of the corresponding vertex.<ref name="Ahmad2014">{{cite journal |last1=Chishti |first1=T. A. |last2=Ganie |first2=Hilal A. |last3=Pirzada |first3=S. |title=Properties of Strong Double Graphs |journal=Journal of Discrete Mathematical Sciences and Cryptography |volume=17 |issue=4 |pages=311–319 |year=2014 |doi=10.1080/09720529.2014.932133 |url=https://www.researchgate.net/publication/281655836_strong_double_graphs}}</ref>

The strong double graph can be expressed as the [lexicographic product](/source/lexicographic_product_of_graphs) <math>SD(G) = G \circ K_2</math>, where <math>K_2</math> is the complete graph on two vertices.<ref name="Ahmad2014"/>

Strong double graphs have several distinct properties:<ref name="Ahmad2014"/>

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

== References ==
{{reflist}}

Category:Graph operations

---
Adapted from the Wikipedia article [Double graph](https://en.wikipedia.org/wiki/Double_graph) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Double_graph?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.