Vernitski, A and Pyatkin, A (2012) 'Astral graphs (threshold graphs), scale-free graphs and related algorithmic questions.' Journal of Discrete Algorithms, 12. 24 - 28. ISSN 1570-8667
Full text not available from this repository.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 > Mathematical Sciences, Department of |
Depositing User: | Jim Jamieson |
Date Deposited: | 12 Feb 2013 17:05 |
Last Modified: | 22 May 2019 10:15 |
URI: | http://repository.essex.ac.uk/id/eprint/5569 |
Actions (login required)
![]() |
View Item |