New measures of graph irregularity
<p>In this paper, we define and compare three new measures of graph irregularity. We use these measures to tighten upper bounds for the chromatic number and the Colin de Verdiere parameter. We also strengthen the concise Turan theorem for irregular graphs and investigate to what extent Turan&#...
| 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
2014-04-01
|
| Series: | Electronic Journal of Graph Theory and Applications |
| Subjects: | |
| Online Access: | https://www.ejgta.org/index.php/ejgta/article/view/50 |
| _version_ | 1818531896169070592 |
|---|---|
| author | Clive Elphick Pawel Wocjan |
| author_facet | Clive Elphick Pawel Wocjan |
| author_sort | Clive Elphick |
| collection | DOAJ |
| description | <p>In this paper, we define and compare three new measures of graph irregularity. We use these measures to tighten upper bounds for the chromatic number and the Colin de Verdiere parameter. We also strengthen the concise Turan theorem for irregular graphs and investigate to what extent Turan's theorem can be similarly strengthened for generalized r-partite graphs. We conclude by relating these new measures to the Randic index and using the measures to devise new normalised indices of network heterogeneity.</p><p> </p> |
| first_indexed | 2024-12-11T17:38:26Z |
| format | Article |
| id | doaj.art-4fc2e08e299347a482f8b496d21556ae |
| institution | Directory Open Access Journal |
| issn | 2338-2287 |
| language | English |
| last_indexed | 2024-12-11T17:38:26Z |
| publishDate | 2014-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-4fc2e08e299347a482f8b496d21556ae2022-12-22T00:56:36ZengIndonesian 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-22872014-04-0121526510.5614/ejgta.2014.2.1.518New measures of graph irregularityClive ElphickPawel Wocjan<p>In this paper, we define and compare three new measures of graph irregularity. We use these measures to tighten upper bounds for the chromatic number and the Colin de Verdiere parameter. We also strengthen the concise Turan theorem for irregular graphs and investigate to what extent Turan's theorem can be similarly strengthened for generalized r-partite graphs. We conclude by relating these new measures to the Randic index and using the measures to devise new normalised indices of network heterogeneity.</p><p> </p>https://www.ejgta.org/index.php/ejgta/article/view/50chromatic number, colin de verdiere parameter, graph irregularity |
| spellingShingle | Clive Elphick Pawel Wocjan New measures of graph irregularity Electronic Journal of Graph Theory and Applications chromatic number, colin de verdiere parameter, graph irregularity |
| title | New measures of graph irregularity |
| title_full | New measures of graph irregularity |
| title_fullStr | New measures of graph irregularity |
| title_full_unstemmed | New measures of graph irregularity |
| title_short | New measures of graph irregularity |
| title_sort | new measures of graph irregularity |
| topic | chromatic number, colin de verdiere parameter, graph irregularity |
| url | https://www.ejgta.org/index.php/ejgta/article/view/50 |
| work_keys_str_mv | AT cliveelphick newmeasuresofgraphirregularity AT pawelwocjan newmeasuresofgraphirregularity |