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

DOI10.5614/EJGTA.2021.9.1.4MaRDI QIDQ4958043zbMATH OpenOpenAlexFDO

Authors Sivakumar Karunakaran, Lavanya Selvaganesh

Publication date 6 September 2021

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

Copyright license Creative Commons Attribution-ShareAlike 4.0 International

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

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)

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.

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

Cites work

• Bounds for the Laplacian spectral radius of graphs
• Combinatorial Matrix Theory and Generalized Inverses of Matrices
• Distance matrices and quadratic embedding of graphs
• Graph theory
• Graph-theoretical matrices in chemistry
• Inverses of triangular matrices and bipartite graphs
• Laplacian matrices of graphs: A survey
• On distance signless Laplacian spectrum and energy of graphs
• On energy, Laplacian energy and \(p\)-fold graphs
• On the spectrum of linear dependence graph of a finite dimensional vector space
• Reciprocal complementary distance spectra and reciprocal complementary distance energy of line graphs of regular graphs
• Squared distance matrix of a weighted tree

Cited in

(2)

• A NOVEL METHOD FOR MEASURING THE STRUCTURAL INFORMATION CONTENT OF NETWORKS
• The neighbor matrix: generalizing a graph's degree sequence

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)