Object
Title: Spanning Trees with few Branch and End Vertices ; Каркасы с меньшим числом висячих и Яг-вершин
Abstract:
For a graph G, let ¾2 be the minimum degree sum of two nonadjacent vertices in G. A vertex of degree one in a tree is called an end vertex and a vertex of degree at least three is called a branch vertex. We consider: (¤) connected graphs on n vertices such that ¾2 ¸ n ¡ k +1 for some positive integer k. In 1976, it was proved (by the author) that every graph satisfying (¤), has a spanning tree with at most k end vertices. In this paper we ¯rst show that every graph satisfying (¤), has a spanning tree with at most k +1 branch and end vertices altogether. The next result states that every graph satisfying (¤), has a spanning tree with at most 1 2 (k ¡ 1) branch vertices. The third result states that every graph satisfying (¤), has a spanning tree with at most 3 2 (k ¡1) degree sum of branch vertices. All results are sharp.
;
Для графа С через а2 обозначается минимальная сумма степеней двух несмежных вершин. Вершина в дереве называется висячей, если имеет степень 1; и называется Яг-вершиной, если имеет степень по меньшей мере 3. В работе рассматриваются только (*) п-вершинные связные графы, удовлетворяющие условию а2 > п — к + 1 для некоторого натурального числа к. В 1976 году была доказана (автором), что произвольный граф удовлетворяющий условию (*), имеет каркас с не более чем к висячими вершинами. В настоящей работе доказывается, что всякий граф удовлетворяющий условию (*), имеет каркас, где общее число висячих и Яг-вершин не превосходит к + 1. Второй результат утверждает, что всякий граф, удовлетворяющий условию (*), имеет каркас, где число Яг-вершин не превосходит ֊ (к — 1). Третий результат утверждает, что всякий граф, удовлетворяющий условию (*), имеет каркас, где сумма степеней Яг-вершин не превосходит ֊ (к — 1). Все три оценки достигаемы.
Publisher:
Mathematical Problems of Computer Science
Identifier:
oai:noad.sci.am:136052
ISSN:
Language:
Volume:
URL:
Additional Information:
Affiliation:
Institute for Informatics and Automation Problems of NAS RA
Country:
Year:
Indexing:
Object collections:
- Digital Library > Academic Insitutions > Insitute for Informatics and Automation Problems of NAS RA > Publications
Last modified:
May 3, 2021
In our library since:
Jul 30, 2020
Number of object content hits:
11
All available object's versions:
https://noad.sci.am/publication/149691
Show description in RDF format:
Show description in OAI-PMH format:
| Edition name | Date |
|---|---|
| Жора Никогосян, Каркасы с меньшим числом висячих и Яг-вершин | May 3, 2021 |
