Authors: Anđelić, Milica
Simić, Slobodan 
Živković, Dejan
Dolićanin, Edin
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

SCOPUSTM   
Citations

3
checked on Jan 16, 2022

Page view(s)

8
checked on Jan 17, 2022

Google ScholarTM

Check

Altmetric

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.