Previous |  Up |  Next


graphic; tree-graphic
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.
[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
Partner of
EuDML logo