{{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}}}}]]

In the mathematical field of graph theory, the '''double graph''' of a 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 of <math>G</math> with the total graph <math>T_2</math>.<ref name="Munarini2008" /> The graph <math>T_2</math> is the complete graph <math>K_2</math> with a loop added to each vertex.

An equivalent construction defines the double graph as the lexicographic product <math>G \circ N_2</math>, where <math>N_2</math> is the 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: 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 <math>A \otimes J_2</math>, where <math>J_2</math> is the 2×2 matrix of ones. * Regularity: 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: <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. * Bipartite graph: <math>G</math> is a bipartite graph if and only if <math>\mathcal{D}[G]</math> is also bipartite. * Spectrum: If the 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: The chromatic number of the double graph is the same as the original graph: <math>\chi(\mathcal{D}[G]) = \chi(G)</math>. * 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 <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) 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 and mathematical chemistry applications.

== Topological indices == Various topological indices 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: <math>W(D[G]) = 4W(G) + 2n</math> * 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: <math>M_1(D[G]) = 8M_1(G)</math> * Second Zagreb index: <math>M_2(D[G]) = 16M_2(G)</math> * Randić 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: <math>S(D[G]) = 8S(G) + 16m</math> * Modified Schultz index: <math>S^*(D[G]) = 16S^*(G) + 8M_1(G)</math> * Szeged index: <math>Sz(D[G]) = 16Sz(G)</math> * 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:<ref name="gm23"/>

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

For the lexicographic product and 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'' 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 <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 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 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