|Title:||Fast algorithms for computing the characteristic polynomial of threshold and chain graphs||Journal:||Applied Mathematics and Computation||Volume:||332||First page:||329||Last page:||337||Issue Date:||1-Sep-2018||Rank:||M21a||ISSN:||0096-3003||DOI:||10.1016/j.amc.2018.03.024||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:||Adjacency matrix | Chain graph | Characteristic polynomial | Graph divisor | Lexicographic product | Threshold graph||Publisher:||Elsevier||Project:||Kuwait University, Grant no. SM06/16|
Show full item record
checked on Jan 16, 2022
checked on Jan 17, 2022
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.