The average order of a subtree of a tree

Andrew Vince; Hua Wang

doi:10.1016/j.jctb.2009.05.006

The average order of a subtree of a tree

Andrew Vince, Hua Wang

Mathematical Sciences

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

50 Scopus citations

Abstract

Let T be a tree all of whose internal vertices have degree at least three. In 1983 Jamison conjectured in JCT B that the average order of a subtree of T is at least half the order of T. In this paper a proof is provided. In addition, it is proved that the average order of a subtree of T is at most three quarters the order of T. Several open questions are stated.

Original language	English
Pages (from-to)	161-170
Number of pages	10
Journal	Journal of Combinatorial Theory. Series B
Volume	100
Issue number	2
DOIs	https://doi.org/10.1016/j.jctb.2009.05.006
State	Published - Mar 2010

Scopus Subject Areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Keywords

Average order
Subtree

Access to Document

10.1016/j.jctb.2009.05.006

Cite this

@article{c42d524e685d4c2788438d8eacae25f2,

title = "The average order of a subtree of a tree",

abstract = "Let T be a tree all of whose internal vertices have degree at least three. In 1983 Jamison conjectured in JCT B that the average order of a subtree of T is at least half the order of T. In this paper a proof is provided. In addition, it is proved that the average order of a subtree of T is at most three quarters the order of T. Several open questions are stated.",

keywords = "Average order, Subtree",

author = "Andrew Vince and Hua Wang",

year = "2010",

month = mar,

doi = "10.1016/j.jctb.2009.05.006",

language = "English",

volume = "100",

pages = "161--170",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "2",

}

TY - JOUR

T1 - The average order of a subtree of a tree

AU - Vince, Andrew

AU - Wang, Hua

PY - 2010/3

Y1 - 2010/3

N2 - Let T be a tree all of whose internal vertices have degree at least three. In 1983 Jamison conjectured in JCT B that the average order of a subtree of T is at least half the order of T. In this paper a proof is provided. In addition, it is proved that the average order of a subtree of T is at most three quarters the order of T. Several open questions are stated.

AB - Let T be a tree all of whose internal vertices have degree at least three. In 1983 Jamison conjectured in JCT B that the average order of a subtree of T is at least half the order of T. In this paper a proof is provided. In addition, it is proved that the average order of a subtree of T is at most three quarters the order of T. Several open questions are stated.

KW - Average order

KW - Subtree

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

U2 - 10.1016/j.jctb.2009.05.006

DO - 10.1016/j.jctb.2009.05.006

M3 - Article

SN - 0095-8956

VL - 100

SP - 161

EP - 170

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

IS - 2

ER -

The average order of a subtree of a tree

Abstract

Scopus Subject Areas

Keywords

Access to Document

Other files and links

Fingerprint

Cite this