Vernitski, Alexei and Pyatkin, Artem (2012) Astral graphs (threshold graphs), scale-free graphs and related algorithmic questions. Journal of Discrete Algorithms, 12. pp. 24-28. DOI https://doi.org/10.1016/j.jda.2011.06.003
Vernitski, Alexei and Pyatkin, Artem (2012) Astral graphs (threshold graphs), scale-free graphs and related algorithmic questions. Journal of Discrete Algorithms, 12. pp. 24-28. DOI https://doi.org/10.1016/j.jda.2011.06.003
Vernitski, Alexei and Pyatkin, Artem (2012) Astral graphs (threshold graphs), scale-free graphs and related algorithmic questions. Journal of Discrete Algorithms, 12. pp. 24-28. DOI https://doi.org/10.1016/j.jda.2011.06.003
Abstract
The astral index of a graph is defined as the smallest number of astral graphs (also known as threshold graphs) into which the graph can be decomposed, divided by the number of vertices in the graph. The astral index is a promising new graph measure for analysing the structure of graphs in applications. In this paper, we prove some theoretical results concerning astral graphs and the astral index. We reveal a connection between astral graphs and scale-free graphs. We prove that finding the exact value of the astral index is an NP-complete problem. © 2011 Elsevier B.V. All rights reserved.
| Item Type: | Article |
|---|---|
| Subjects: | Q Science > QA Mathematics |
| Divisions: | Faculty of Science and Health Faculty of Science and Health > Mathematical Sciences, Department of |
| SWORD Depositor: | Unnamed user with email elements@essex.ac.uk |
| Depositing User: | Unnamed user with email elements@essex.ac.uk |
| Date Deposited: | 12 Feb 2013 17:05 |
| Last Modified: | 15 Jan 2022 00:47 |
| URI: | http://repository.essex.ac.uk/id/eprint/5569 |