Double graph explained

is a graph derived from

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

l{D}[G]

, of a simple graph

is formally defined as the direct product of

with the total graph

T₂

. The graph

T₂

is the complete graph

K₂

with a loop added to each vertex.

G\circN₂

, where

N₂

is the null graph on two vertices (two vertices with no edges).

If a graph

has

vertices and

edges, its double graph

l{D}[G]

has

vertices and

edges.

Properties

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

Adjacency matrix: If

is the adjacency matrix of

, then the adjacency matrix of

l{D}[G]

is the Kronecker product

A ⊗ J₂

, where

J₂

is the 2×2 matrix of ones.

Regularity: A graph

-regular if and only if its double

l{D}[G]

-regular.

Connectivity:

is connected if and only if

l{D}[G]

is connected. Furthermore, if

is connected, then

l{D}[G]

is Eulerian.

Bipartite graph:

is a bipartite graph if and only if

l{D}[G]

is also bipartite.

Spectrum: If the eigenvalues of

are

λ_1,...,λ_n

, the spectrum of

l{D}[G]

consists of the eigenvalues

2λ_1,...,2λ_n

and

additional eigenvalues equal to zero.

Chromatic number: The chromatic number of the double graph is the same as the original graph:

\chi(l{D}[G])=\chi(G)

Isomorphism: Two graphs,

G₁

and

G₂

, are isomorphic if and only if their doubles,

l{D}[G_1]

and

l{D}[G_2]

, are isomorphic.

Example

K_n

. The resulting graph,

l{D}[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.^[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

with

vertices:^[3]

Wiener index:

W(D[G])=4W(G)+2n

Harary index:

H(D[G])=4H(G)+n/2

Degree-based indices

For a graph

:^[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\sqrt{

	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

with

edges:^[3]

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:

GA_2(D[G])=4GA_2(G)

Eccentric connectivity index

For a connected graph

with

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₁

and

G₂

:^[3]

	c(D[G
\xi
	1

\circG_2])=w(G_1)(4n

	2(n

	1

-1)+8m₂₎+

	2\xi
4n
	2

	c(G

	1)

+8m_2\zeta(G₁₎

	c(D[G
\xi
	1

\boxplusG_2])=16|E(G₁\boxplusG_2)|

where

n_i=|V(G_i)|

m_i=|E(G_i)|

, and

\zeta(G₁₎

is the total eccentricity of

G₁

Strong double graph

While the double graph of a graph

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]

SD(G)=G\circK₂

, where

K₂

is the complete graph on two vertices.^[4]

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

Size: If

has

vertices and

edges, then

SD(G)

has

vertices and

4m+n

edges.

Bipartiteness:

SD(G)

is bipartite if and only if

is totally disconnected (i.e.,

G=\overline{K_n}

Hamiltonian property:

SD(G)

is Hamiltonian if and only if

is connected with at least one vertex.

Chromatic number: For any graph

with at least one edge,

4\leq\chi(SD(G))\leq2\Delta(G)+2

, where

\Delta(G)

is the maximum degree of

Connectivity: The connectivity of

SD(G)

\kappa(SD(G))=2\kappa(G)

Notes and References

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