A unique and novel graph matrix for efficient extraction of structural information of networks
<p class="p1">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,<span class="Apple-converted-space"...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Indonesian Combinatorial Society (InaCombS); Graph Theory and Applications (GTA) Research Centre; University of Newcastle, Australia; Institut Teknologi Bandung (ITB), Indonesia
2021-04-01
|
| Series: | Electronic Journal of Graph Theory and Applications |
| Subjects: | |
| Online Access: | https://www.ejgta.org/index.php/ejgta/article/view/679 |
| _version_ | 1811250768947183616 |
|---|---|
| author | Sivakumar Karunakaran Lavanya Selvaganesh |
| author_facet | Sivakumar Karunakaran Lavanya Selvaganesh |
| author_sort | Sivakumar Karunakaran |
| collection | DOAJ |
| description | <p class="p1">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,<span class="Apple-converted-space"> </span>called as neighbourhood matrix <em>NM</em>(<em>G</em>).<span class="Apple-converted-space"> </span>The proposed matrix also exhibits a<span class="Apple-converted-space"> </span>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 <em>NM</em>(<em>G</em>). Additionally, we also show how to reconstruct a graph <em>G</em>, given an <em>NM</em>(<em>G</em>). The proposed matrix also solves many graph-theoretic problems using less time complexity in comparison to the existing algorithms.</p> |
| first_indexed | 2024-04-12T16:09:35Z |
| format | Article |
| id | doaj.art-1884caf4115f4c0fa5a907cbb7e6f740 |
| institution | Directory Open Access Journal |
| issn | 2338-2287 |
| language | English |
| last_indexed | 2024-04-12T16:09:35Z |
| publishDate | 2021-04-01 |
| publisher | Indonesian Combinatorial Society (InaCombS); Graph Theory and Applications (GTA) Research Centre; University of Newcastle, Australia; Institut Teknologi Bandung (ITB), Indonesia |
| record_format | Article |
| series | Electronic Journal of Graph Theory and Applications |
| spelling | doaj.art-1884caf4115f4c0fa5a907cbb7e6f7402022-12-22T03:25:57ZengIndonesian Combinatorial Society (InaCombS); Graph Theory and Applications (GTA) Research Centre; University of Newcastle, Australia; Institut Teknologi Bandung (ITB), IndonesiaElectronic Journal of Graph Theory and Applications2338-22872021-04-0191395110.5614/ejgta.2021.9.1.4200A unique and novel graph matrix for efficient extraction of structural information of networksSivakumar Karunakaran0Lavanya Selvaganesh1SRM Research Institute, SRM Institute of Science and Technology, Kattankulathur, Chennai, IndiaAssistant Professor, Department of Mathematical Sciences, IIT (BHU), Varanasi-221005, Uttar Pradesh, India<p class="p1">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,<span class="Apple-converted-space"> </span>called as neighbourhood matrix <em>NM</em>(<em>G</em>).<span class="Apple-converted-space"> </span>The proposed matrix also exhibits a<span class="Apple-converted-space"> </span>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 <em>NM</em>(<em>G</em>). Additionally, we also show how to reconstruct a graph <em>G</em>, given an <em>NM</em>(<em>G</em>). The proposed matrix also solves many graph-theoretic problems using less time complexity in comparison to the existing algorithms.</p>https://www.ejgta.org/index.php/ejgta/article/view/679graph matricesgraph characterizationmatrix productgraph propertiesstrongly regular graphsc4-free |
| spellingShingle | Sivakumar Karunakaran Lavanya Selvaganesh A unique and novel graph matrix for efficient extraction of structural information of networks Electronic Journal of Graph Theory and Applications graph matrices graph characterization matrix product graph properties strongly regular graphs c4-free |
| title | A unique and novel graph matrix for efficient extraction of structural information of networks |
| title_full | A unique and novel graph matrix for efficient extraction of structural information of networks |
| title_fullStr | A unique and novel graph matrix for efficient extraction of structural information of networks |
| title_full_unstemmed | A unique and novel graph matrix for efficient extraction of structural information of networks |
| title_short | A unique and novel graph matrix for efficient extraction of structural information of networks |
| title_sort | unique and novel graph matrix for efficient extraction of structural information of networks |
| topic | graph matrices graph characterization matrix product graph properties strongly regular graphs c4-free |
| url | https://www.ejgta.org/index.php/ejgta/article/view/679 |
| work_keys_str_mv | AT sivakumarkarunakaran auniqueandnovelgraphmatrixforefficientextractionofstructuralinformationofnetworks AT lavanyaselvaganesh auniqueandnovelgraphmatrixforefficientextractionofstructuralinformationofnetworks AT sivakumarkarunakaran uniqueandnovelgraphmatrixforefficientextractionofstructuralinformationofnetworks AT lavanyaselvaganesh uniqueandnovelgraphmatrixforefficientextractionofstructuralinformationofnetworks |