Arbres avec un nombre maximum de sommets pendants
type: Item
instance of: scholarly article
title: Arbres avec un nombre maximum de sommets pendants
zbMATH Open document ID: 0539.05037
DOI: 10.1016/0012-365X(84)90163-8
author: N. E. Zubov
published in: Discrete Mathematics
publication date: 1984-01-01T00:00:00Z
review text: 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''.
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 3857148
zbMATH Keywords: spanning tree
zbMATH Keywords: maximum degree
zbMATH Keywords: pendant vertices
reviewed by: R. C. Entringer
MaRDI profile type: Publication
cites work: Q4096964
cites work: Self-stabilizing systems in spite of distributed control
cites work: Two-Processor Scheduling with Start-Times and Deadlines
cites work: Q3928248
cites work: Q4073393
description: scientific article; zbMATH DE number 3857148