Maximizing the number of spanning trees in \(K_n\)-complements of asteroidal graphs

DOI10.1016/j.disc.2008.08.008zbMath1229.05150OpenAlexW2114318330MaRDI QIDQ1025922

Stavros D. Nikolopoulos, Leonidas Palios, Charis Papadopoulos

Publication date: 23 June 2009

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2008.08.008

zbMATH Keywords

interconnection networksmaximizationspanning treescomplement-spanning-tree matrixstar-like graphs

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35)

Related Items (7)

On two conjectures concerning spanning tree edge dependences of graphs ⋮ Counting spanning trees using modular decomposition ⋮ The number of spanning trees of the Cartesian product of regular graphs ⋮ The maximum number of spanning trees of a graph with given matching number ⋮ An efficient approach for counting the number of spanning trees in circulant and related graphs ⋮ The number of spanning trees of a graph with given matching number ⋮ Counting Spanning Trees in Graphs Using Modular Decomposition

Cites Work

• 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
• On the number of spanning trees of a multi-complete/star related graph
• On the number of spanning trees and Eulerian tours in iterated line digraphs
• The number of spanning trees in \(K_ n\)-complements of quasi-threshold graphs
• Parallel concepts in graph theory
• On the characterization of graphs with maximum number of spanning trees
• The number of spanning trees in circulant graphs
• Some methods for counting the spanning trees in labelled molecular graphs, examined in relation to certain fullerenes
• A limit characterization for the number of spanning trees of graphs
• Chebyshev polynomials and spanning tree formulas for circulant and related graphs
• On the number of spanning trees in directed circulant graphs
• Uniformly-most reliable networks do not always exist
• On unreliability polynomials and graph connectivity in reliable network synthesis
• Maximizing spanning trees in almost complete graphs

This page was built for publication: Maximizing the number of spanning trees in \(K_n\)-complements of asteroidal graphs