On majorization of closed walk vectors of trees with given degree sequences

Ya Hong Chen; Daniel Gray; Ya Lei Jin; Xiao Dong Zhang

doi:10.1016/j.amc.2018.05.007

On majorization of closed walk vectors of trees with given degree sequences

Ya Hong Chen, Daniel Gray, Ya Lei Jin, Xiao Dong Zhang

Mathematical Sciences

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

1 Scopus citations

Abstract

Let C_v(k; T) be the number of closed walks of length k starting at vertex v in a tree T. We prove that for any tree T with a given degree sequence π, the vector C(k; T) ≡ (C_v(k; T), v ∈ V(T)) is weakly majorized by the vector C(k;T_π ^*)≡(C_v(k;T_π ^*),v∈V(T_π ^*)), where T_π ^* is the greedy tree with the degree sequence π. In addition, for two trees degree sequences π and π′, if π is majorized by π′, then C(k;T_π ^*) is weakly majorized by C(k;T_π^′ ^*).

Original language	English
Pages (from-to)	326-337
Number of pages	12
Journal	Applied Mathematics and Computation
Volume	336
DOIs	https://doi.org/10.1016/j.amc.2018.05.007
State	Published - Nov 1 2018

Keywords

Closed walk
Degree sequence
Majorization
Trees

Access to Document

10.1016/j.amc.2018.05.007

Cite this

@article{0483425c185343c492fb919a77ffdc9f,

title = "On majorization of closed walk vectors of trees with given degree sequences",

abstract = "Let Cv(k; T) be the number of closed walks of length k starting at vertex v in a tree T. We prove that for any tree T with a given degree sequence π, the vector C(k; T) ≡ (Cv(k; T), v ∈ V(T)) is weakly majorized by the vector C(k;Tπ *)≡(Cv(k;Tπ *),v∈V(Tπ *)), where Tπ * is the greedy tree with the degree sequence π. In addition, for two trees degree sequences π and π′, if π is majorized by π′, then C(k;Tπ *) is weakly majorized by C(k;Tπ′ *).",

keywords = "Closed walk, Degree sequence, Majorization, Trees",

author = "Chen, {Ya Hong} and Daniel Gray and Jin, {Ya Lei} and Zhang, {Xiao Dong}",

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

year = "2018",

month = nov,

day = "1",

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

language = "English",

volume = "336",

pages = "326--337",

journal = "Applied Mathematics and Computation",

issn = "0096-3003",

publisher = "Elsevier Inc.",

}

TY - JOUR

T1 - On majorization of closed walk vectors of trees with given degree sequences

AU - Chen, Ya Hong

AU - Gray, Daniel

AU - Jin, Ya Lei

AU - Zhang, Xiao Dong

PY - 2018/11/1

Y1 - 2018/11/1

N2 - Let Cv(k; T) be the number of closed walks of length k starting at vertex v in a tree T. We prove that for any tree T with a given degree sequence π, the vector C(k; T) ≡ (Cv(k; T), v ∈ V(T)) is weakly majorized by the vector C(k;Tπ *)≡(Cv(k;Tπ *),v∈V(Tπ *)), where Tπ * is the greedy tree with the degree sequence π. In addition, for two trees degree sequences π and π′, if π is majorized by π′, then C(k;Tπ *) is weakly majorized by C(k;Tπ′ *).

AB - Let Cv(k; T) be the number of closed walks of length k starting at vertex v in a tree T. We prove that for any tree T with a given degree sequence π, the vector C(k; T) ≡ (Cv(k; T), v ∈ V(T)) is weakly majorized by the vector C(k;Tπ *)≡(Cv(k;Tπ *),v∈V(Tπ *)), where Tπ * is the greedy tree with the degree sequence π. In addition, for two trees degree sequences π and π′, if π is majorized by π′, then C(k;Tπ *) is weakly majorized by C(k;Tπ′ *).

KW - Closed walk

KW - Degree sequence

KW - Majorization

KW - Trees

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

U2 - 10.1016/j.amc.2018.05.007

DO - 10.1016/j.amc.2018.05.007

M3 - Article

AN - SCOPUS:85047649029

SN - 0096-3003

VL - 336

SP - 326

EP - 337

JO - Applied Mathematics and Computation

JF - Applied Mathematics and Computation

ER -

On majorization of closed walk vectors of trees with given degree sequences

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this