Counting spanning trees in graphs using modular decomposition

DOI10.1007/978-3-642-19094-0_21MaRDI QIDQ3078398zbMATH OpenOpenAlexFDO

Authors Stavros D. Nikolopoulos, Leonidas Palios, 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

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Enumeration in graph theory (05C30)

Recommendations

• Counting spanning trees using modular decomposition
• Counting spanning trees in cographs: an algorithmic approach
• scientific article; zbMATH DE number 2127724
• \(P_ 4\)-trees and substitution decomposition
• Linear algebraic techniques for spanning tree enumeration

Cites work

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

Cited in

(2)

• Counting spanning trees in cographs: an algorithmic approach
• Counting spanning trees using modular decomposition

This page was built for publication: Counting spanning trees in graphs using modular decomposition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3078398)