Counting spanning trees using modular decomposition

DOI10.1016/J.TCS.2014.01.012MaRDI QIDQ2437761zbMATH OpenOpenAlexFDO

Authors Stavros D. Nikolopoulos, Leonidas Palios, Charis Papadopoulos

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 algorithms\(P_4\)-tidy graphnumber of spanning treestree-cograph\((q,q-4)\)-graphKirchhoff matrix tree theorem

Mathematics Subject Classification ID

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

Recommendations

• Counting spanning trees in graphs using modular decomposition
• Counting spanning trees in cographs: an algorithmic approach
• scientific article; zbMATH DE number 2127724
• \(P_ 4\)-trees and substitution decomposition
• Enumeration of spanning trees of certain graphs

Cites work

• scientific article; zbMATH DE number 3906240 (Why is no real title available?)
• scientific article; zbMATH DE number 1375569 (Why is no real title available?)
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 3637904 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1456953 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization.
• A New Class of Brittle Graphs
• A formula for the number of spanning trees of a multi-star related graph
• 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
• A survey of the algorithmic aspects of modular decomposition
• 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
• Computing the treewidth and the minimum fill-in with the modular decomposition
• Drawing graphs using modular decomposition
• Efficient algorithms for graphs with few \(P_4\)'s
• Generalized Nested Dissection
• Laplacian spectrum of weakly quasi-threshold graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Matching theory
• Maximizing the number of spanning trees in \(K_n\)-complements of asteroidal graphs
• Modular decomposition and transitive orientation
• On semi-\(P_ 4\)-sparse graphs
• On the number of spanning trees of multi-star related graphs
• On the structure of graphs with few \(P_4\)s
• Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
• 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
• Tree- and forest-perfect graphs
• Uniformly-most reliable networks do not always exist

Cited in

(4)

• The number and degree distribution of spanning trees in the Tower of Hanoi graph
• The number of spanning trees for Sierpiński graphs and data center networks
• Counting spanning trees in cographs: an algorithmic approach
• Counting spanning trees in graphs using modular decomposition

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

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