標題: 小型籠的連通數
Connectivity of Small Cages
作者: 李育明
Yu-Ming Lee
傅恆霖
黃國卿
Hung-Lin Fu
Kuo-Ching Huang
應用數學系所
關鍵字: 籠;連通數;正則;cage;connectivity;regular
公開日期: 2002
摘要: 一個度數為δ的正則圖, 如果最小圈的長度為g, 則此圖形稱為(δ,g)-圖. 而其中點數最少的稱為(δ,g)-籠. 一個圖若是每個切集至少包含有κ個點的話, 則此圖形為κ-連通. Marcote等人證明了, 當δ≧5且g≧10的時候, (δ,g)-籠為4-連通, 在這篇論文中, 我們證明每一個δ≧5的(δ,8)-籠和(δ,9)-籠都是4-連通.
A regular graph G of degree δ and girth g is said to be a (δ, g)-graph, and a (δ, g)- cage is a smallest graph among all (δ, g)-graphs. A graph is κ-connected if every cutset has cardinality at least κ. It was proved by Marcote et al that a (δ, g)-cage is 4-connected provided that δ≧5 and g≧10. In this thesis, we prove that every (δ, 8)-cage and (δ, 9)-cage is 4-connected with δ≧5.
URI: http://140.113.39.130/cdrfb3/record/nctu/#NT910507016
http://hdl.handle.net/11536/70949
顯示於類別:畢業論文