半徑為3以下的中點圖

Median graphs of radius at most three

洪湧昇(Yung-Sheng Hung)

指導教授 ： 翁志文

國立交通大學/理學院/應用數學系暨研究所/碩士(2012年)

https://doi.org/10.6842/NCTU.2012.00457

摘要

中點圖已經被研究數十年，許多中點圖的理論及性質已經被發表，而其大部分的理論都和其具”凸”性質的某些子圖有關。我們試著用不同的角度去研究半徑不超過3 的圖，過程中不用到”凸”性質並且試著找出這些圖是中點圖的充分且必要條件。

關鍵字

中點圖

並列摘要

Median graphs have been studied for decades. Many important theorems
and properties of median graphs have been found out and almost all
of those theorems are relative to convex. We try to study median graphs in a different way. We consider median graphs with radius at most 3
and try to find out their necessary and sufficient conditions without using convex property.

並列關鍵字

Median graph

參考文獻

[2] H.M. Mulder, The structure of median graphs, Discrete Math., 24 (1978), 197-204.

[3] H.M. Mulder, n-Cubes and median graphs, J. Graph Theory, 4 (1980),

[4] J. Hagauer, W. Imrich, S. Klavžar, Recognizing median graphs in subquadratic time, Theoretical Computer Science, 215 (1999), 123-126.

[5] W. Imrich, S. Klavžar, H.M. Mulder, Median graphs and triangle-free graphs, SIAM J. Discrete Math., 12 (1999), 111-118

[1] L. Nebesky, Median graphs, Comment. Math. Univ. Carolinae, 12 (1971), 317-325.