scientific article; zbMATH DE number 140143
[For the entire collection see Zbl 0747.00036.] The topic of spanning trees has been a popular one for some time. Much work, starting as early as 1964 [\textit{S. L. Harkini} and \textit{D. G. Green}, Generation and realization of trees and \(k\)-trees, IEEE Trans. Circuit Theory, CT-11, 247-255 (1964)], has been done on the subject of finding algorithms which count the number of spanning trees in a given graph. \textit{A. D. Kelmans} and \textit{V. M. Chelnokov} [J. Comb. Theory, Ser. B 16, 197-214 (1974; Zbl 0277.05104)] found that a graph obtained by deleting several mutually nonadjacent edges from the complete graph has the maximum number of spanning trees among simple graphs with the same number of vertices and edges. \textit{C.-S. Cheng} [J. Comb. Theory. Ser. B 31, 240-248 (1981; Zbl 0475.05050)] extended this to show that a regular complete \(k\)-partite graph is the unique simple graph with the maximum nubmer of spanning trees among graphs with the same number of vertices and edges. In \textit{C.-S. Cheng}, \textit{J. C. Masaro} and \textit{C. S. Wong} [J. Graph Theory 9, 342-345 (1985; Zbl 0583.05022)] he further developed this problem to include the fact that nearly balanced multigraphs have more spanning trees. There has also been substantial research done on cycles in graphs and their extremal properties. For example, the family of cubic graphs with the fewest number of cycles was found in \textit{C. A. Barefoot}, \textit{L. Clark} and \textit{R. Entringer} [Combinatorics, graph theory, and computing, Proc. 17th Southeast. Conf. Boca Raton/Fl. 1986, Congr. Numerantium 53, 49-62 (1986; Zbl 0623.05033)]. Corresponding results for spanning trees in cubic graphs will be found in this paper.
- scientific article; zbMATH DE number 4008429
- On the minimum number of spanning trees in cubic multigraphs
- Spanning trees with many leaves in cubic graphs
- Cubic graphs with minimum number of spanning trees.
- On homeomorphically irreducible spanning trees in cubic graphs
- Extremal graphs for a spectral inequality on edge-disjoint spanning trees
- scientific article; zbMATH DE number 861398
- Spanning trees in subcubic graphs.
- On the spanning trees of the hypercube and other products of graphs
- The extremal average distance of cubic graphs
- The minimum number of spanning trees in regular multigraphs
- On the minimum number of spanning trees in cubic multigraphs
- Cubic graphs with minimum number of spanning trees.
- Do nearly balanced multigraphs have more spanning trees?
- scientific article; zbMATH DE number 4008429 (Why is no real title available?)
- scientific article; zbMATH DE number 55681 (Why is no real title available?)
- Maximizing spanning trees in almost complete graphs
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4028527)