Arbres avec un nombre maximum de sommets pendants (Q793746): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Q4096964 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Self-stabilizing systems in spite of distributed control / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Two-Processor Scheduling with Start-Times and Deadlines / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3928248 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4073393 / rank | |||
Normal rank |
Latest revision as of 12:53, 14 June 2024
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
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