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:

0131-4645

Language:

English

Volume:

46

URL:

click here to follow the link

Additional Information:

zhora@ipia.sci.am

Affiliation:

Institute for Informatics and Automation Problems of NAS RA

Country:

Armenia

Year:

2016

Indexing:

ASCI

Object collections:

Last modified:

May 3, 2021

In our library since:

Jul 30, 2020

Number of object content hits:

7

All available object's versions:

https://noad.sci.am/publication/149691

Show description in RDF format:

RDF

Show description in OAI-PMH format:

OAI-PMH

This page uses 'cookies'. More information