Double graph
In the mathematical field of graph theory, the double graph of a simple graph 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.
Definition
The double graph, denoted as, of a simple graph is formally defined as the direct product of with the total graph. The graph is the complete graph with a loop added to each vertex.An equivalent construction defines the double graph as the lexicographic product, where is the null graph on two vertices.
If a graph has vertices and edges, its double graph 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 is the Kronecker product, where is the 2×2 matrix of ones.
- Regularity: A graph is -regular if and only if its double is -regular.
- Connectivity: is connected if and only if is connected. Furthermore, if is connected, then is Eulerian.
- Bipartite graph: is a bipartite graph if and only if is also bipartite.
- Spectrum: If the eigenvalues of are, the spectrum of consists of the eigenvalues and additional eigenvalues equal to zero.
- Chromatic number: The chromatic number of the double graph is the same as the original graph:.
- Isomorphism: Two graphs, and, are isomorphic if and only if their doubles, and, are isomorphic.
Example
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 and quantitative structure-property relationships, where the biological activity or other properties of molecules are correlated with their chemical structure.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. These graph operations allow researchers to understand how topological properties of composite graphs relate to the properties of their simpler constituent graphs, which is particularly useful in chemical graph theory and mathematical chemistry applications.
Topological indices
Various topological indices have been studied for double graphs. 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:- Wiener index:
- Harary index:
Degree-based indices
- First Zagreb index:
- Second Zagreb index:
- Randić index:
- Atom-bond connectivity index:
- Geometric-arithmetic index:
Combined degree-distance indices
- Schultz index:
- Modified Schultz index:
- Szeged index:
- Padmakar-Ivan index:
- Second geometric-arithmetic index:
Eccentric connectivity index
For the lexicographic product and complete sum of graphs and :
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 joins each vertex with the closed neighborhood of the corresponding vertex.The strong double graph can be expressed as the lexicographic product, where is the complete graph on two vertices.
Strong double graphs have several distinct properties:
- Size: If has vertices and edges, then has vertices and edges.
- Bipartiteness: is bipartite if and only if is totally disconnected.
- Hamiltonian property: is Hamiltonian if and only if is connected with at least one vertex.
- Chromatic number: For any graph with at least one edge,, where is the maximum degree of.
- Connectivity: The connectivity of is.