Achiral plane trees

Research output: Contribution to journalArticleResearchpeer-review

1 Citation (Scopus)

Abstract

Harary and Robinson showed that the number an of achiral planted plane trees with n points coincides with the number pn of achiral plane trees with n points, for n ⩾ 2. They posed the problem of finding a natural structural correspondence which explains this coincidence. In the present paper this problem is answered by constructing two‐to‐one correspondences from certain sets of binary sequences to each of the sets of trees concerned, giving a structural basis for the equation 2an = 2pn. Answers are also supplied to similar correspondence‐type problems of Harary and Robinson, concerning planted plane trees, and achiral rooted plane trees. In addition, each of these four types of plane trees are counted with numbers of points and endpoints as the enumeration parameters. The results all show a symmetry with respect to the number of endpoints which is not shared by the set of all plane trees.

Original languageEnglish
Pages (from-to)189-208
Number of pages20
JournalJournal of Graph Theory
Volume2
Issue number3
DOIs
Publication statusPublished - 1978
Externally publishedYes

Cite this

Wormald, Nicholas. / Achiral plane trees. In: Journal of Graph Theory. 1978 ; Vol. 2, No. 3. pp. 189-208.
@article{c6575cb02aea4d74b558889027399706,
title = "Achiral plane trees",
abstract = "Harary and Robinson showed that the number an of achiral planted plane trees with n points coincides with the number pn of achiral plane trees with n points, for n ⩾ 2. They posed the problem of finding a natural structural correspondence which explains this coincidence. In the present paper this problem is answered by constructing two‐to‐one correspondences from certain sets of binary sequences to each of the sets of trees concerned, giving a structural basis for the equation 2an = 2pn. Answers are also supplied to similar correspondence‐type problems of Harary and Robinson, concerning planted plane trees, and achiral rooted plane trees. In addition, each of these four types of plane trees are counted with numbers of points and endpoints as the enumeration parameters. The results all show a symmetry with respect to the number of endpoints which is not shared by the set of all plane trees.",
author = "Nicholas Wormald",
year = "1978",
doi = "10.1002/jgt.3190020303",
language = "English",
volume = "2",
pages = "189--208",
journal = "Journal of Graph Theory",
issn = "0364-9024",
publisher = "John Wiley & Sons",
number = "3",

}

Achiral plane trees. / Wormald, Nicholas.

In: Journal of Graph Theory, Vol. 2, No. 3, 1978, p. 189-208.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Achiral plane trees

AU - Wormald, Nicholas

PY - 1978

Y1 - 1978

N2 - Harary and Robinson showed that the number an of achiral planted plane trees with n points coincides with the number pn of achiral plane trees with n points, for n ⩾ 2. They posed the problem of finding a natural structural correspondence which explains this coincidence. In the present paper this problem is answered by constructing two‐to‐one correspondences from certain sets of binary sequences to each of the sets of trees concerned, giving a structural basis for the equation 2an = 2pn. Answers are also supplied to similar correspondence‐type problems of Harary and Robinson, concerning planted plane trees, and achiral rooted plane trees. In addition, each of these four types of plane trees are counted with numbers of points and endpoints as the enumeration parameters. The results all show a symmetry with respect to the number of endpoints which is not shared by the set of all plane trees.

AB - Harary and Robinson showed that the number an of achiral planted plane trees with n points coincides with the number pn of achiral plane trees with n points, for n ⩾ 2. They posed the problem of finding a natural structural correspondence which explains this coincidence. In the present paper this problem is answered by constructing two‐to‐one correspondences from certain sets of binary sequences to each of the sets of trees concerned, giving a structural basis for the equation 2an = 2pn. Answers are also supplied to similar correspondence‐type problems of Harary and Robinson, concerning planted plane trees, and achiral rooted plane trees. In addition, each of these four types of plane trees are counted with numbers of points and endpoints as the enumeration parameters. The results all show a symmetry with respect to the number of endpoints which is not shared by the set of all plane trees.

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

U2 - 10.1002/jgt.3190020303

DO - 10.1002/jgt.3190020303

M3 - Article

VL - 2

SP - 189

EP - 208

JO - Journal of Graph Theory

JF - Journal of Graph Theory

SN - 0364-9024

IS - 3

ER -