scientific article; zbMATH DE number 140143

From MaRDI portal
Publication:4028527





[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.











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)