Arbres avec un nombre maximum de sommets pendants (Q793746)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Arbres avec un nombre maximum de sommets pendants
scientific article

    Statements

    Arbres avec un nombre maximum de sommets pendants (English)
    0 references
    0 references
    1984
    0 references
    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''.
    0 references
    spanning tree
    0 references
    maximum degree
    0 references
    pendant vertices
    0 references

    Identifiers