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

Sivakumar Karunakaran, Lavanya Selvaganesh


In this article, we propose a new type of square matrix associated with an undirected graph by trading off the natural embedded symmetry in them. The proposed matrix is defined using the neighbourhood sets of the vertices,  called as neighbourhood matrix NM(G).  The proposed matrix also exhibits a  bijection between the product of the two graph matrices, namely the adjacency matrix and the graph Laplacian. Alternatively, we define this matrix by using the breadth-first search traversals from every vertex, and the subgraph induced by 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 neighbours along with the neighbours-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 properties of NM(G). Additionally, we also show how to reconstruct a graph G, given an  NM(G). The proposed matrix also solves many graph-theoretic problems using less time complexity in comparison to the existing algorithms.


graph matrices; graph characterization; matrix product; graph properties; strongly regular graphs; C4-free

Full Text:


DOI: http://dx.doi.org/10.5614/ejgta.2021.9.1.4


Abdollah Alhevaz, Maryam Baghipur and Ebrahim Hashemi, On distance signless Laplacian spectrum and energy of graphs, Electron. J. Graph Theory Appl. 6 (2) (2018), 326–340.

R.B. Bapat, Graphs and matrices, Springer, (2014).

R.B. Bapat, Squared distance matrix of a weighted tree, Electron. J. Graph Theory Appl. 7 (2) (2019), 301–313.

R.B. Bapat, S. J. Kirkland, K.M. Prasath and S. Puntanen (Eds), Combinatorial Matrix Theory and generalized inverses of matrices, Springer India, (2013).

J.A. Bondy and U.S.R. Murty, Graph Theory: Graduate Texts in Mathematics, Springer, (2008).

Hilal A. Ganie, Shariefuddin Pirzada and Edy Tri Baskoro, On energy, Laplacian energy and $p$-fold graphs, Electron. J. Graph Theory Appl. 3 (1) (2015), 94–107.

D. Janezic, A. Milicevic, S.Nikolic and N.Trinajstic, Graph Theoretical Matrices in Chemistry, Mathematical Chemistry Monographs 3 (2007).

Sushobhan Maity and A. K. Bhuniya, On the spectrum of linear dependence graph of a finite dimensional vector space, Electron. J. Graph Theory Appl. 7 (1) (2019), 43–59.

Russell Merris, The Laplacian matrices of graphs: a survey,

Linear Algebra and its Applications (197-198) (1994), 143-176.

Nobuaki Obata and Alfi Y. Zakiyyah, Distance matrices and quadratic embedding of graphs, Electron. J. Graph Theory Appl. 6 (1) (2018), 37–60.

Kamal Lochan Patra and Binod Kumar Sahoo, Bounds for the Laplacian spectral radius of graphs, Electron. J. Graph Theory Appl. 5 (2) (2017), 276–303.

Georgios A. Pavlopoulos, Maria Secrier, Charalampos N Moschopoulos, Theodoros G Soldatos, Sophia Kossida, Jan Aerts, Reinhard Schneider and Pantelis G Bagos, Using graph theory to analyze biological networks, BioData Mining, 4:10 (2011).

Harishchandra S. Ramane, Ashwini S. Yalnaik, Reciprocal complementary distance spectra and reciprocal complementary distance energy of line graphs of regular graphs, Electron. J. Graph Theory Appl. 3 (2) (2015), 228–236.

D. B. West, Introduction to Graph Theory, Pearson, 2 (2000).


  • There are currently no refbacks.

ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats