Premium
Maximizing spanning trees in almost complete graphs
Author(s) -
Gilbert Bryan,
Myrvold Wendy
Publication year - 1997
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199708)30:1<23::aid-net3>3.0.co;2-n
Subject(s) - spanning tree , combinatorics , mathematics , complement (music) , trémaux tree , simple (philosophy) , simple graph , arboricity , discrete mathematics , algebraic number , minimum degree spanning tree , graph , minimum spanning tree , pathwidth , line graph , planar graph , biochemistry , chemistry , philosophy , epistemology , complementation , gene , phenotype , mathematical analysis
We examine the family of graphs whose complements are a union of paths and cycles and develop a very simple algebraic technique for comparing the number of spanning trees. With our algebra, we can obtain a simple proof of a result of Kel'mans that evening out path lengths increases the number of spanning trees in the complement graph. We provide similar characterizations for cycles. The theorems that we develop enable us to characterize the graphs in this family with a maximum number of spanning trees. © 1997 John Wiley & Sons, Inc. Networks 30:23–30, 1997