A unique and novel graph matrix for efficient extraction of structural information of networks

DOI10.5614/EJGTA.2021.9.1.4zbMATH Open1468.05158arXiv1903.05341OpenAlexW3159540101MaRDI QIDQ4958043FDOQ4958043

Authors: Sivakumar Karunakaran, Lavanya Selvaganesh 

Publication date: 6 September 2021

Published in: Electronic Journal of Graph Theory and Applications (Search for Journal in Brave)

Abstract: In this article, we propose a new type of square matrix associated with an undirected graph by trading off the naturally imbedded symmetry in them. The proposed matrix is defined using the neighbourhood sets of the vertices. It is called as neighbourhood matrix and it is denoted by $mathcalNM(G)$ as this proposed matrix also exhibits a bijection between the product of the two graph matrices, namely the adjacency matrix and the graph Laplacian. This matrix can also be obtained by looking at every vertex and the subgraph with vertices from the first two levels in the level decomposition from that vertex. The two levels in the level decomposition of the graph give us more information about the neighbour of a vertex along with the neighbour of neighbour of a vertex. This insight is required and is found useful in studying the impact of broadcasting on social networks, in particular, and complex networks, in general. We establish several interesting properties of the $mathcalNM(G)$. In addition, we also show how to reconstruct a graph $G$, given a $mathcalNM(G)$. The proposed matrix is also found to solve many graph theoretic problems using less time complexity in comparison to the existing algorithms.

Full work available at URL: https://arxiv.org/abs/1903.05341

Recommendations

• The neighbor matrix: generalizing a graph's degree sequence
• scientific article; zbMATH DE number 7341332
• scientific article; zbMATH DE number 3991549
• scientific article; zbMATH DE number 1185293
• The anti-adjacency matrix of a graph: eccentricity matrix

zbMATH Keywords

strongly regular graphsmatrix productgraph characterizationgraph propertiesgraph matrices\(C_4\)-free

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Distance in graphs (05C12) Graph representations (geometric and intersection representations, etc.) (05C62) Structural characterization of families of graphs (05C75)

Cites Work

• Graph theory
• Laplacian matrices of graphs: A survey
• On energy, Laplacian energy and p-fold graphs
• Squared distance matrix of a weighted tree
• Inverses of triangular matrices and bipartite graphs
• Graph-theoretical matrices in chemistry
• Bounds for the Laplacian spectral radius of graphs
• Distance matrices and quadratic embedding of graphs
• Combinatorial Matrix Theory and Generalized Inverses of Matrices
• On distance signless Laplacian spectrum and energy of graphs
• Reciprocal Complementary Distance Spectra and Reciprocal Complementary Distance Energy of Line Graphs of Regular Graphs
• On the spectrum of linear dependence graph of a finite dimensional vector space

Cited In (1)

• A NOVEL METHOD FOR MEASURING THE STRUCTURAL INFORMATION CONTENT OF NETWORKS

This page was built for publication: A unique and novel graph matrix for efficient extraction of structural information of networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4958043)