Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8900949 | Applied Mathematics and Computation | 2018 | 9 Pages |
Abstract
The characteristic polynomial of a graph is the characteristic polynomial of its adjacency matrix. Finding efficient algorithms for computing characteristic polynomial of graphs is an active area of research and for some graph classes, like threshold graphs, there exist very fast algorithms which exploit combinatorial structure of the graphs. In this paper, we put forward some novel ideas based on divisor technique to obtain fast algorithms for computing the characteristic polynomial of threshold and chain graphs.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Applied Mathematics
Authors
M. AnÄeliÄ, S.K. SimiÄ, D. ŽivkoviÄ, E.Ä. DoliÄanin,