On the nullity number of graphs
The paper discusses bounds on the nullity number of graphs. It is proved in [B. Cheng and B. Liu, On the nullity of graphs. Electron. J. Linear Algebra 16 (2007) 60--67] that $\eta \le n - D$, where $\eta$, n and D denote the nullity number, the order and the diameter of a connected graph, respectiv...
| 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
2017-10-01
|
| Series: | Electronic Journal of Graph Theory and Applications |
| Subjects: | |
| Online Access: | https://www.ejgta.org/index.php/ejgta/article/view/202 |
| _version_ | 1811250727061815296 |
|---|---|
| author | Mustapha Aouchiche Pierre Hansen |
| author_facet | Mustapha Aouchiche Pierre Hansen |
| author_sort | Mustapha Aouchiche |
| collection | DOAJ |
| description | The paper discusses bounds on the nullity number of graphs. It is proved in [B. Cheng and B. Liu, On the nullity of graphs. Electron. J. Linear Algebra 16 (2007) 60--67] that $\eta \le n - D$, where $\eta$, n and D denote the nullity number, the order and the diameter of a connected graph, respectively. We first give a necessary condition on the extremal graphs corresponding to that bound, and then we strengthen the bound itself using the maximum clique number. In addition, we prove bounds on the nullity using the number of pendant neighbors in a graph. One of those bounds is an improvement of a known bound involving the domination number. |
| first_indexed | 2024-04-12T16:08:57Z |
| format | Article |
| id | doaj.art-6d822a39672841ab81a3d061faf7c033 |
| institution | Directory Open Access Journal |
| issn | 2338-2287 |
| language | English |
| last_indexed | 2024-04-12T16:08:57Z |
| publishDate | 2017-10-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-6d822a39672841ab81a3d061faf7c0332022-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-22872017-10-015233534610.5614/ejgta.2017.5.2.14100On the nullity number of graphsMustapha Aouchiche0Pierre Hansen1GERAD and HEC Montreal, CanadaGERAD and HEC Montreal, CanadaThe paper discusses bounds on the nullity number of graphs. It is proved in [B. Cheng and B. Liu, On the nullity of graphs. Electron. J. Linear Algebra 16 (2007) 60--67] that $\eta \le n - D$, where $\eta$, n and D denote the nullity number, the order and the diameter of a connected graph, respectively. We first give a necessary condition on the extremal graphs corresponding to that bound, and then we strengthen the bound itself using the maximum clique number. In addition, we prove bounds on the nullity using the number of pendant neighbors in a graph. One of those bounds is an improvement of a known bound involving the domination number.https://www.ejgta.org/index.php/ejgta/article/view/202adjacency matrix, nullity number, diameter, matching number, pendant neighbor, domination number |
| spellingShingle | Mustapha Aouchiche Pierre Hansen On the nullity number of graphs Electronic Journal of Graph Theory and Applications adjacency matrix, nullity number, diameter, matching number, pendant neighbor, domination number |
| title | On the nullity number of graphs |
| title_full | On the nullity number of graphs |
| title_fullStr | On the nullity number of graphs |
| title_full_unstemmed | On the nullity number of graphs |
| title_short | On the nullity number of graphs |
| title_sort | on the nullity number of graphs |
| topic | adjacency matrix, nullity number, diameter, matching number, pendant neighbor, domination number |
| url | https://www.ejgta.org/index.php/ejgta/article/view/202 |
| work_keys_str_mv | AT mustaphaaouchiche onthenullitynumberofgraphs AT pierrehansen onthenullitynumberofgraphs |