Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
graphic; tree-graphic
graphic; tree-graphic
Summary:
We give a necessary and sufficient condition for the existence of a tree of order $n$ with a given degree set. We relate this to a well-known linear Diophantine problem of Frobenius.
References:
[1] T. S. Ahuja, A. Tripathi: On the order of a graph with a given degree set. The Journal of Combinatorial Mathematics and Combinatorial Computing 57 (2006), 157–162. MR 2226692
[2] P. Erdös, T. Gallai: Graphs with prescribed degrees of vertices. Mat. Lapok 11 (1960), 264–274. (Hungarian)
[3] R. K. Guy: Unsolved Problems in Number Theory. Unsolved Problems in Intuitive Mathematics, Volume I, Third Edition. Springer-Verlag, New York, 2004. MR 2076335
[4] S. L. Hakimi: On the realizability of a set of integers as degrees of the vertices of a graph. J. SIAM Appl. Math. 10 (1962), 496–506. DOI 10.1137/0110037 | MR 0148049
[5] V. Havel: A remark on the existence of finite graphs. Čas. Pěst. Mat. 80 (1955), 477–480. (Czech)
[6] S. F. Kapoor, A. D. Polimeni, and C. E. Wall: Degree sets for graphs. Fund. Math. 95 (1977), 189–194. DOI 10.4064/fm-95-3-189-194 | MR 0480200
Search
Partner of
