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]

Definition

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]

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]

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).

References

  1. ^ Munarini, Emanuele; Cippo, Claudio Perelli; Scagliola, Andrea; Salvi, Norma Zagaglia (2008). "Double graphs". Discrete Mathematics. 308 (2): 242–254. doi:10.1016/j.disc.2006.11.038
  2. ^ Azari, Mahdieh (2022). "Three Constructions on Graphs and Distance-Based Invariants". Mathematics Interdisciplinary Research. 7: 89–103. doi:10.22052/MIR.2021.242881.1292
  3. ^ Ghasemi, Mehdi & Madanshekaf, Ali (27 September 2023). "On the Topological Indices on Double Graphs". Caspian Journal of Mathematical Sciences. 12 (2): 423–439. doi:10.22080/CJMS.2023.25624.1660
  4. ^ Chishti, T. A.; Ganie, Hilal A.; Pirzada, S. (2014). "Properties of Strong Double Graphs". Journal of Discrete Mathematical Sciences and Cryptography. 17 (4): 311–319. doi:10.1080/09720529.2014.932133