Abstract:

A tree with at most k leaves is called a k-ended tree. Let tk be the order of a largest k-ended tree in a graph. A tree T of a graph G is said to be dominating if V(G — T ) is an independent set of vertices. The minimum degree sum of any pair (triple) of nonadjacent vertices in G will be denoted by a σ2 (σ3). The earliest result concerning spanning trees with few leaves (by the author, 1976) states: (*) if G is a connected graph of order n with a σ2 > n — k + 1 for some positive integer k, then G has a spanning k-ended tree. In this paper we show: (г) the connectivity condition in (*) can be removed; (ii) the condition a 2 > n — k + 1 in (*) can be relaxed by replacing n with tk+1 ; (iii) if G is a connected graph with σ3 > tk+i — 2k + 4 for some integer k > 2, then G has a dominating k-ended tree. All results are sharp.
; Дерево с не более чем k-висячими вершинами называется k-висячим деревом. Число верш и н максимального k-висячего дерева обозначается через tk. Через σ 2 (σ 3) обозначается минимальная сумма с тепеней двух (трех) попарно не см еж ны х вершин. Дерево T в графе G называется доминантным, если V(G-T) является н е зависимым м н оже ст вом вершин. В 1976 году д о к а зан о (автором): (*) если n вершинный связный гр аф G удовлетворяе т условию σ 2 > n — k + 1 для некоторого целого числа k, то G содержи т k-висячое о сто вн ое дерево. В насто ящей работедоказывается , что условие с вязности в (*) можно опускать. Второй результат я вляется усилением (*) с помощью замены n через tk+ 1 (напомним, что tk+ 1 < n). Приводится такж е версия второго результата для доминантных k-висячих деревьев . Все результаты неулучшаемы.

Date submitted:

06 .11 .2014

Date accepted:

28 .01 .2015

Identifier:

oai:noad.sci.am:136012

ISSN:

0131-4645

Language:

English

Journal or Publication Title:

Mathematical Problems of Computer Science

Volume:

43

URL:

Additional Information:

zhora@ipia.sci.am

Affiliation:

Institute for Informatics and Automation Problems

Country:

Armenia

Indexing:

ASCI