No label defined (Q4028527)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 140143
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 140143

      Statements

      0 references
      28 March 1993
      0 references
      spanning trees
      0 references
      extremal properties
      0 references
      cubic graphs
      0 references
      [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.
      0 references

      Identifiers