Arbres avec un nombre maximum de sommets pendants (Q793746): Difference between revisions

In connection with work of \textit{E. W. Dijkstra} [Commun. ACM 17, 643-644 (1974; Zbl 0305.68048)] on stability in systems with distributed control \textit{M. Tchuente} [RAIRO, Inf. Théor. 15, 47-66 (1981; Zbl 0473.68047)] posed the problem of finding a spanning tree of a given connected graph G for which the product of the degrees of the vertices was minimum. The authors consider the case in which G has maximum degree 3, where the problem reduces to that of finding a spanning tree with the maximum number of vertices of degree 3 since in any spanning tree of such a graph, the number of pendant vertices is 2 more than the number of vertices of degree 3. It is shown that G has a spanning tree containing at least one fourth of the vertices of degree 3 of G and conjectured that this can be improved to one third if G does not contain \(K_ 4-e\). In the prefacing paragraph ''degree 1'' should be changed to ''degree 3''.