臺灣博碩士論文加值系統

假設G 是ㄧ個圖，x 為G 中的頂點，定義x 到它的最遠距離點的距離為x 的離心率。若頂點x 為周圍點，必須滿足鄰點的離心率皆小於或等於x 點的離心率。對於任意兩個頂點，我們稱作ㄧ條x-y 的測地線為ㄧ條x 到y 的最短路徑。令I[x,y]是指收集在所有x-y 測地線上頂點的點子集。假設S 為圖G 的點子集，那麼I[S]為所有在S 中的頂點x 和y 所形成的I[x,y]的聯集。且如果I[S]恰等於圖G 的點集合時，則可稱S 為圖G 的測地線集。在這篇論文中，我們研究乘積圖中的周圍集，並且在一些特定條件下，去討論圖的周圍集為測地線集。

For a vertex x of G, the eccentricity e (x) is the distance between x and a
vertex farthest from x. Then x is a contour vertex if there is no neighbor of
x with its eccentricity greater than e (x). The x-y path of length d (x,y) is
called a x-y geodesic. The geodetic interval I [x,y] of a graph G is the set
of vertices of all x-y geodesics in G. For S ⊆
V , the geodetic closure I [S]
of S is the union of all geodetic intervals I [x,y] over all pairs x,y ∈S. A
vertex set S is a geodetic set for G if I [S] = V (G). In this thesis, we study
the contour sets of product graphs and discuss these sets are geodetic sets
for some conditions.

Abstract---{4}
(1) Introduction---{ 5}
(2) Previous results---{10}
(3) The main results ---{12}
(4) Conclusion ---{20}
References ---{21}

G. Abay-Asmerom, R. Hammack, Centers of tensor products of graphs, Ars Combin. 74 (2005), 201-211.
F. Buckley, F. Harary, Distance in graphs, Addison-Wesley Publishing Company, Advanced Book Program, Redwood City, CA, 1990.
G. Chartrand, D. Erwin, G.L. Johns, P. Zhang, Boundary vertices in graphs, Discrete Math. 263 (2003), no. 1-3, 25-34.
J. Cceres, C. Hernando, M. Mora, I. M. Pelayo, M. L. Puertas, C. Seara, On geodetic sets formed by boundary vertices, Discrete Math. 306 (2006), no. 2, 188-198.
J. Cceres, C. Hernando, M. Mora, I. M. Pelayo, M. L. Puertas, C. Seara, Geodeticity of the contour of chordal graphs, Discrete Appl. Math. 156 (2008), no. 7, 1132-1142 .
G. Chartrand, F. Harary, P. Zhang, Geodetic sets in graphs, Discuss. Math. Graph Theory 20 (2000), 129-138.
G. Chartrand, L. Lesniak, Graphs & digraphs, Third edition. Chapman & Hall, London, 1996.
J. Cceres, A. Mrquez, O. R. Oellerman, M. L. Puertas, Rebuilding convex sets in graphs, Discrete Math. 297 (2005), no. 1-3, 26-37.
W. Imrich, S. Klavar, Product graphs, Structure and recognition, With a foreword by Peter Winkler. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York, 2000.