Counting Spanning Trees in Graphs Using Modular Decomposition

DOI10.1007/978-3-642-19094-0_21zbMath1318.05082MaRDI QIDQ3078398

Leonidas Palios, Stavros D. Nikolopoulos, Charis Papadopoulos

Publication date: 20 February 2011

Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-19094-0_21

Mathematics Subject Classification ID

05C05: Trees

05C30: Enumeration in graph theory

05C85: Graph algorithms (graph-theoretic aspects)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the number of spanning trees of multi-star related graphs
• The number of spanning trees in \(K_ n\)-complements of quasi-threshold graphs
• Matrix multiplication via arithmetic progressions
• An efficient approach for counting the number of spanning trees in circulant and related graphs
• Laplacian spectrum of weakly quasi-threshold graphs
• Maximizing the number of spanning trees in \(K_n\)-complements of asteroidal graphs
• Strong tree-cographs are Birkhoff graphs
• Modular decomposition and transitive orientation
• A new technique for the characterization of graphs with a maximum number of spanning trees
• On the structure of graphs with few \(P_4\)s
• Computing the treewidth and the minimum fill-in with the modular decomposition
• The number of spanning trees in circulant graphs
• A new approach to solving three combinatorial enumeration problems on planar graphs
• Some methods for counting the spanning trees in labelled molecular graphs, examined in relation to certain fullerenes
• Linear time solvable optimization problems on graphs of bounded clique-width
• Chebyshev polynomials and spanning tree formulas for circulant and related graphs
• Uniformly-most reliable networks do not always exist
• Generalized Nested Dissection
• Algebraic Graph Theory
• Drawing graphs using modular decomposition
• Computer Science Logic