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
28 March 1993
0 references
spanning trees
0 references
extremal properties
0 references
cubic graphs
0 references
0.92397046
0 references
0.90680784
0 references
0.89570475
0 references
0.88939625
0 references
0.88634753
0 references
0 references
0.8814634
0 references
0.87978816
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