Number of vertices of degree three in spanning 3-trees in square graphs

被引：0

作者：

Aye, Win Min ^{[1
]}

Tian, Tao ^{[2
]}

Xiong, Liming ^{[2
]}

机构：

[1] Ka Lay Univ, Math Dept, Kalay, Myanmar

[2] Beijing Inst Technol, Sch Math & Stat, Beijing Key Lab MCAACI, Beijing 10248, Peoples R China

来源：

APPLIED MATHEMATICS AND COMPUTATION | 2019年 / 357卷

关键词：

Square graph; 3-tree; Spanning tree; MAXIMUM DEGREE; TREES;

D O I：

10.1016/j.amc.2019.03.062

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

In this paper, we show that the square graph of a tree T has a spanning tree of maximum degree at most three and with at most max {0, Sigma(x is an element of W >= 3) ((T)) (t(T) (x)-2)-2} vertices of degree three, where W->= 3 (T) = {x is an element of V (T) : there are at least three edge-disjoint paths of length at least two that start x} and t(T)(x) is the number of edge-disjoint paths with length at least two that start at a vertex x. (c) 2019 Elsevier Inc. All rights reserved.

引用

页码：258 / 262

页数：5

共 12 条

[1] Maximal trees with bounded maximum degree in a graph [J].

Aung, M ;

Kyaw, A .

GRAPHS AND COMBINATORICS, 1998, 14 (03) :209-221

[2]

Bondy J.A., 2008, GRADUATE MATH, V244

[3]

Broersma H, 1998, J GRAPH THEOR, V29, P227, DOI 10.1002/(SICI)1097-0118(199812)29:4<227::AID-JGT2>3.3.CO

[4]

2-N

[5] ON THE LARGEST TREE OF GIVEN MAXIMUM DEGREE IN A CONNECTED GRAPH [J].

CARO, Y ;

KRASIKOV, I ;

RODITTY, Y .

JOURNAL OF GRAPH THEORY, 1991, 15 (01) :7-13

[6]

Fleischner H., 1974, Journal of Combinatorial Theory, Series B, V16, P29, DOI 10.1016/0095-8956(74)90091-4

[7]

NEUMANNLARA V, 1991, COMBINATORICA, V11, P55, DOI 10.1007/BF01375473

[8]

Ore O., 1960, Am Math Monthly, V67, P55, DOI [10.2307/2308928, DOI 10.2307/2308928]

[9] A note on a spanning 3-tree [J].

Tsugaki, Masao .

COMBINATORICA, 2009, 29 (01) :127-129

[10]

Win S., 1979, RESULTATE MATH, V2, P215

← 1 2 →