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

Win Min Aye; Tao Tian; Liming Xiong

doi:10.1016/j.amc.2019.03.062

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

Win Min Aye, Tao Tian, Liming Xiong^*

^*Corresponding author for this work

School of Mathematics and Statistics

Research output: Contribution to journal › Article › peer-review

Abstract

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,∑ _{x∈W _≥3 (T)} (t _T (x)−2)−2} vertices of degree three, where W _≥3 (T)={x∈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.

Original language	English
Pages (from-to)	258-262
Number of pages	5
Journal	Applied Mathematics and Computation
Volume	357
DOIs	https://doi.org/10.1016/j.amc.2019.03.062
Publication status	Published - 15 Sept 2019

Keywords

3-tree
Spanning tree
Square graph

Access to Document

10.1016/j.amc.2019.03.062

Cite this

Aye, W. M., Tian, T., & Xiong, L. (2019). Number of vertices of degree three in spanning 3-trees in square graphs. Applied Mathematics and Computation, 357, 258-262. https://doi.org/10.1016/j.amc.2019.03.062

@article{7396ff2262a24a88a26f9b79a5e91062,

title = "Number of vertices of degree three in spanning 3-trees in square graphs",

abstract = " 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,∑ x∈W ≥3 (T) (t T (x)−2)−2} vertices of degree three, where W ≥3 (T)={x∈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.",

keywords = "3-tree, Spanning tree, Square graph",

author = "Aye, {Win Min} and Tao Tian and Liming Xiong",

note = "Publisher Copyright: {\textcopyright} 2019 Elsevier Inc.",

year = "2019",

month = sep,

day = "15",

doi = "10.1016/j.amc.2019.03.062",

language = "English",

volume = "357",

pages = "258--262",

journal = "Applied Mathematics and Computation",

issn = "0096-3003",

publisher = "Elsevier Inc.",

}

TY - JOUR

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

AU - Aye, Win Min

AU - Tian, Tao

AU - Xiong, Liming

PY - 2019/9/15

Y1 - 2019/9/15

N2 - 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,∑ x∈W ≥3 (T) (t T (x)−2)−2} vertices of degree three, where W ≥3 (T)={x∈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.

AB - 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,∑ x∈W ≥3 (T) (t T (x)−2)−2} vertices of degree three, where W ≥3 (T)={x∈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.

KW - 3-tree

KW - Spanning tree

KW - Square graph

UR - http://www.scopus.com/inward/record.url?scp=85064172897&partnerID=8YFLogxK

U2 - 10.1016/j.amc.2019.03.062

DO - 10.1016/j.amc.2019.03.062

M3 - Article

AN - SCOPUS:85064172897

SN - 0096-3003

VL - 357

SP - 258

EP - 262

JO - Applied Mathematics and Computation

JF - Applied Mathematics and Computation

ER -

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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this