Mathematics

Two-degree trees

  • Pu QIAO ,
  • Xingzhi ZHAN
Expand
  • 1. School of Mathematics, East China University of Science and Technology, Shanghai 200237, China
    2. School of Mathematical Sciences, East China Normal University, Shanghai 200241, China

Received date: 2021-05-07

  Online published: 2023-03-23

Abstract

A graph is called a two-degree graph if its vertices have only two distinct degrees. A two-degree tree of order at least three have two degrees, $ 1 $ and $ d $ for some $ d\geqslant 2; $ such a tree is called a $ (1,d) $ -tree. Given a positive integer $ n, $ we determine: (1) the possible values of $ d $ such that there exists a $ (1,d) $ -tree of order $ n; $ (2) the values of $ d $ such that there exists a unique $ (1,d) $ -tree of order $ n $ , and (3) the maximum diameter of two-degree trees of order $ n. $ The results provide a new example showing that the behavior of graphs may sometimes be determined by number theoretic properties.

Cite this article

Pu QIAO , Xingzhi ZHAN . Two-degree trees[J]. Journal of East China Normal University(Natural Science), 2023 , 2023(2) : 1 -4 . DOI: 10.3969/j.issn.1000-5641.2023.02.001

References

1 BONDY J A, MURTY U S R. Graph Theory [M]. New York: Springer, 2008.
2 BLASS A, HARARY F, MILLER Z. Which trees are link graphs?. Journal of Combinatorial Theory (Series B), 1980, 29, 277- 292.
3 BROERSMA H, XIONG L, YOSHIMOTO K. Toughness and hamiltonicity in k-trees . Discrete Math, 2007, 307, 832- 838.
Outlines

/