Counting spanning trees using modular decomposition

DOI10.1016/j.tcs.2014.01.012zbMath1283.05134OpenAlexW2049204396MaRDI QIDQ2437761

Leonidas Palios, Charis Papadopoulos, Stavros D. Nikolopoulos

Publication date: 13 March 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.01.012

zbMATH Keywords

modular decompositionlinear-time algorithmsnumber of spanning trees\(P_4\)-tidy graphtree-cograph\((q,q-4)\)-graphKirchhoff matrix tree theorem

Mathematics Subject Classification ID

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

Related Items

The number and degree distribution of spanning trees in the Tower of Hanoi graph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the number of spanning trees of multi-star related graphs
• A formula for the number of spanning trees of a multi-star related graph
• A survey of the algorithmic aspects of modular decomposition
• The number of spanning trees in \(K_ n\)-complements of quasi-threshold graphs
• 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
• Matching theory
• Strong tree-cographs are Birkhoff graphs
• Modular decomposition and transitive orientation
• Tree- and forest-perfect graphs
• A new technique for the characterization of graphs with a maximum number of spanning trees
• On semi-\(P_ 4\)-sparse graphs
• On the structure of graphs with few \(P_4\)s
• Computing the treewidth and the minimum fill-in with the modular decomposition
• (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization.
• 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
• A New Class of Brittle Graphs
• Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
• Generalized Nested Dissection
• Drawing graphs using modular decomposition
• Efficient algorithms for graphs with few \(P_4\)'s