摘要(英) |
Abstract
B. Zelinka [Zel] showed that the median of any tree is equal to its centroid. A. Kang and D. Ault [Kang] extended this result for any tree with weights on its edges. In Chapter 2, we extend the result further to any tree with
weights on its edges and vertices and show that the second median of any tree with weights on its vertices is equal to its second centroid. The main result in Chapter 3 is that if S is a spider, T is a tree and S , T have the same status sequence,than S is isomorphic to T . In Chapter 4, we show that if T is a weakly
status-injective tree, T’’ is a tree, and T ,T’’ have thesame status sequence, then T is isomorphic to T’’. The main result in Chapter 5 is that if two spiders have the same branch-weight-sequence, then they are isomorphic. |
參考文獻 |
References
1.
[Buckley] F. Buckley and F. Harary, Distance in Graphs, Addison-Wesley
Publishing company (1990).
2.
[Band] H-J Bandelt and V. Chepo, Graphs with connected medians,
SIAM J. Discrete Math, Vol. 15, 268-282 (2002).
3.
[Ent] R. C. Entringer, Albuquerque, D. E. Jackson, Los Alamos, D. A.
snyder, Distance in graphs, Czech. Math. J. 26, 283-296 (1976).
4.
[Gold] A. J. Goldman, Minimax location of a facility in a network,
Transportation Science 6, 407-418 (1972).
5.
[Hak] S. L. Hakimi, Optimum locations of switching centers and medians
of a graph, Operation Research 12, 450-459 (1964).
6.
[Kang] Andy N. C. Kang and David A. Ault, Some properties of a centroid
of a free tree, Information Processing Lett. 4, No. 1, 18-20 (1975).
7.
[Lee] H-Y Lee and G. J. Chang, The w-median of a connected strongly
chordal graph, J. Graph Theory Vol. 18, No. 7, 673-680 (1994).
8.
[Mit] S. L. Mitchell, Another characterization of the centroid
of a tree, Discrete Math. 24, No. 3, 277-280 (1978).
9.
[Mill] Z. Miller, Medians and distance sequence in graphs, Ars
Combin. 15, 169-177 (1983).
10.
[Piot] W. Piotrowski and M. M. Syslo, A characterization of
centroidal graphs, Combinatorial Optimization, 272-281 (1986).
11.
[Pach] L. Pachter, Constructing status injective graphs, Discrete
Appl. Math. 80, 107-113 (1997).
12.
[Slater1] P. J. Slater, Maximin facility location, J. Mathematical
Sciences, Vol. 79 B, No. 3 and 4 (1975).
13.
[Slater2] P. J. Slater, Medians of arbitrary graphs, J. Graph Theory
Vol. 4, 389-392 (1980).
14.
[Slater3] P. J. Slater, Counterexamples to Randic's conjecture on distance
degree sequences for trees, J. Graph Theory 6, 89-91 (1982).
15.
[Sk1] R. Skurnick, Extending the concept of branch-weight centroid
number to the vertices of all connected graphs via the slater number,
Graph Theory Notes of New York, 33, 28-32 (1997).
16.
[Sk2] R. Skurnick, A characterization of the centroid sequence of a
caterpillar, Graph Theory Notes of New York, 41, 7-13 (2001).
17.
[Zel] B. Zelinka, Medians and peripherians of trees, Arch Math. 4, 87
-95 (1968). |