小型籠的連通數

Abstract

一個度數為δ的正則圖, 如果最小圈的長度為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.