Chordal 2‐Connected Graphs and Spanning Trees |
| |
| Authors: | Zbigniew R Bogdanowicz |
| |
| Affiliation: | ARMAMENT RESEARCH, DEVELOPMENT AND ENGINEERING CENTER, PICATINNY, NJ |
| |
| Abstract: | We present a transformation on a chordal 2‐connected simple graph that decreases the number of spanning trees. Based on this transformation, we show that for positive integers n, m with  , the threshold graph  having n vertices and m edges that consists of an  ‐clique and  vertices of degree 2 is the only graph with the fewest spanning trees among all 2‐connected chordal graphs on n vertices and m edges. |
| |
| Keywords: | chordal graph spanning tree enumeration of trees threshold graph minimization shift transformation 05C45 05C38 |
|
|
