A characteristic polynomial for rooted graphs and rooted digraphs

Downloadable Content

Download this item
Abstract
  • We consider the one-variable characteristic polynomial p(G; lambda) in two settings. When G is a rooted digraph, we show that this polynomial essentially counts the number of sinks in G. When G is a rooted graph, we give combinatorial interpretations of several coefficients and the degree of p(G; lambda). Ln particular, /p(G; 0)/ is the number of acyclic orientations of G, while the degree of p(G; lambda) gives the size of the minimum tree cover (every edge of G is adjacent to some edge of T), and the leading coefficient gives the number of such covers. Finally, we consider the class of rooted fans in detail; here p(G; lambda) shows cyclotomic behavior.
TitleA characteristic polynomial for rooted graphs and rooted digraphs
CreatorMcMahon, Elizabeth
Gordon, Gary
PublisherDiscrete Mathematics
Academic DepartmentMathematics
DivisionNatural Sciences
OrganizationLafayette College
Date Issued2001
Date Available2018-12-21T15:50:36Z
TypeArticle
LanguageEnglish
Keywordcharacteristic polynomial
rooted graph
rooted digraph
branching greedoid
Bibliographic CitationGordon, G. and E. McMahon (2001) "A characteristic polynomial for rooted graphs and rooted digraphs." Discrete Mathematics 232 (1-3): 19-33.
Standard IdentifierDOI 10.1016/S0012-365X(00)00186-2
Handle 10385/2491
Permalinkhttp://hdl.handle.net/10385/2491
Rights Statement In Copyright In Copyright
Rights HoldersElsevier Science B. V.
Contains
File Gordon-DiscreteMathematics-vol232-2001.pdf Uploaded 2019-10-20 Public Download

Member of Collection

Faculty Publications

View Collection