| Title:
|
Graphic sequences of trees and a problem of Frobenius (English) |
| Author:
|
Gupta, Gautam |
| Author:
|
Joshi, Puneet |
| Author:
|
Tripathi, Amitabha |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
57 |
| Issue:
|
1 |
| Year:
|
2007 |
| Pages:
|
49-52 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
graphic |
| Keyword:
|
tree-graphic |
| MSC:
|
05C07 |
| idZBL:
|
Zbl 1174.05023 |
| idMR:
|
MR2309947 |
| . |
| Date available:
|
2009-09-24T11:43:39Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/128153 |
| . |
| Reference:
|
[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 |
| Reference:
|
[2] P. Erdös, T. Gallai: Graphs with prescribed degrees of vertices.Mat. Lapok 11 (1960), 264–274. (Hungarian) |
| Reference:
|
[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 |
| Reference:
|
[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. MR 0148049, 10.1137/0110037 |
| Reference:
|
[5] V. Havel: A remark on the existence of finite graphs.Čas. Pěst. Mat. 80 (1955), 477–480. (Czech) |
| Reference:
|
[6] S. F. Kapoor, A. D. Polimeni, and C. E. Wall: Degree sets for graphs.Fund. Math. 95 (1977), 189–194. MR 0480200, 10.4064/fm-95-3-189-194 |
| . |
