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). Все три оценки достигаемы.

Mathematical Problems of Computer Science

46

click here to follow the link

zhora@ipia.sci.am

Institute for Informatics and Automation Problems of NAS RA

Armenia

2016

ASCI