この論文では以下に述べる問題を扱った。(この論文では、ループあるいは多重辺をもたない、有限な有向でないグラフだけを考える。)

　直径及び連結度はともにグラフに関する重要なパラメタである。これらはそれぞれ通信における伝送遅延(transmission delay)および障害耐性(fault tolerance)の問題と関係があり、コンピューターサイエンスの発展に伴いますます注目されるようになってきた。直径と連結度とを統合した概念である広義直径(wide diameter、何通りかの概念が存在する)は、1991年にD.F.Hsuによって明瞭な形で提出されて以来、広く研究されてきた。(その前にも多くの研究者がこれに関連する研究を行っている。)([M-P88],[H91],[H94])

　x、yをグラフGの異なる頂点とするとき、C(x,y)がxとyの間のcontainerであるとは、C(x,y)がxとyの間の通路からなる集合であり、かつP、P’をC(x,y)に含まれる任意の二つの通路とするとき、PとP’がx,y以外に頂点を共有しないことをいう。C(x,y)に含まれる通路の本数をC(x,y)の幅といい、w(C(x,y))と書く、またC(x,y)に含まれる最も長い通路の長さをC(x,y)の長さといい、‖C(x,y)‖と書く。xとyの間の幅kのcontainer C(x,y)の長さの最小値をxとyの間のk-距離といい、d_k(x,y)と書く。すなわち

　である。Gのk-直径d_k(G)を

　で定義する。一方、障害耐性直径と呼ばれるもう一つの広義直径の概念の定義は次の通りである。Gの異なる頂点x,yに対して

　とおき、

　と定める。をxとyの間の(k-1)-障害距離といい、をGの(k-1)-障害直径という。

　[H-Z95]において、与えられたn、dに対して、頂点数がnでk-直径がd(または(k-1)-障害直径がd)のk-連結グラフの大きさ(辺の数)の最大値が決定された。これに対し、この論文の1.2ではそのようなグラフの大きさの最小値を調べる。

　および

　とおこう。このときこの論文では次を証明する。

　定理1. (本文中のTheorem1.2.2とTheorem1.2.6参照)

　次のいずれの場合においてもl_f(n,k)＝k(n-k)が成立する。

　定理2.(本文中のTheorem1.2.8参照)

　また[H-L94]においてはk-正則k-連結グラフのk-直径の最大値が調べられている。

　とおこう。これに関して[H-L94]の主要結果は次の通りであった。

　Fact1.

　これに対し、この論文の1.3では次のことを証明する。

　定理3.(本文中のTheorem1.3.1、1.3.7、1.3.8、1.3.9参照)

　定理4.(本文中のTheorem1.3.10参照)S(k)＝{a(k-1)+b+1|a,b∈N,2a+b≦k-3}とおくとき、k≧6かつm∈S(k)ならばf_reg(2m,k)<mである。特に7≦k+1≦m≦2k-5ならばf_reg(2m,k)<mである。

　頂点直径臨界グラフ(vertex diameter critical graph)も[M68]などの研究者により研究されている。グラフGが頂点直径臨界グラフであるとは、任意の∈V(G)に対しd(G-)>d(G)が成立することをいう。VDC(d)を直径がdであるような頂点直径臨界グラフG全体の集合とする。A.Boals、N.SherwaniおよびH.Aliは[B-S-A90]においてG∈VDC(2)に対しが成立すると予想した。この論文の1.4では頂点直径臨界グラフの概念を次のように頂点k-直径臨界グラフと呼ばれるものに拡張する。k≧1とするとき、Gが頂点k-直径臨界グラフであるとは、任意の∈V(G)に対しd_k(G-)>d_k(G)が成立することをいう。(k,d)をk-直径がdであるような頂点k-直径臨界グラフ全体の集合とする。このときこの論文では次を証明した。k＝1とおくことにより、[B-S-A90]の予想が正しくないことがわかる。

　定理5.(本文中のTheorem1.4.8参照)k≧1かつn≧55k-14のとき、(k,2)に属し少なくとも本の辺を持つ頂点数nのグラフが構成できる。

　定理6.(本文中のTheorem1.4.9参照)k≧2かつ10k-4≦n≦55k-15のとき、次の(1)-(6)のおのおのの場合に応じて、(k,2)に属し次のf(n)本の辺を持つ頂点数nのグラフが構成できる。

　極値グラフ理論における最も難しい問題の一つにつぎのErdos-Sos予想である。

　予想(Erdos-Sos).頂点数がnで辺の数がより多いグラフは、辺の数がkのすべての木を部分グラフとして含む。

　これに関連してDobsonは博士論文および[B-D]において次の予想を提出した。

　(Dobson).Gをg(G)≧2t+1を満たすグラフ(g(G)はGのgirth)とし、Tを辺の数がkの木とする。このときかつ(G)≧(T)ならばGはTを部分グラフとして含む。

　[B-D]は、このDobsonの予想のt＝2の場合を、条件(G)≧(T)をより弱い要請(G)≧(T)に置き換えた上で証明したまたこれを用いてErdos-Sos予想をgirthが5以上の場合に証明した。

　これに対し、この論文の第2部では次を証明する。

　定理7.(本文中のTheorem2.3.1参照)Gをg(G)≧7を満たすグラフとし、Tを辺の数がkの木とする。このときならばGはTを部分グラフとして含む。

　以下ではm-部グラフK_t,t,…,tをと書く。

　この論文の第3部ではグラフの三角形分解を論じ、次を証明する。ここでグラフG＝(V,E)が三角形分解可能であるとは、E(G)の集合としての分割であって、その各ブロックAが{xy,yz,xz}の形の辺の集合である(すなわちG[A]が位数3の完全グラフK₃である)ようなものが存在することをいう。

　定理8.(本文中のLemma3.3.1とTheorem3.3.12参照)

　定理9.(本文中のTheorem3.3.6とTheorem3.3.10参照)

　n≧p+1、pが偶数でかつ6|pnとするとき、頂点数がnのp-正則グラフであって三角形分解可能なものが存在する。

　本論文は、グラフのwide diameterに関する最大最小問題を始め、3種類のグラフ理論に関する問題を扱ったものである。

　論文の第1部はwide diameterに関する最大最小問題にあてられている。wide diameterはグラフの直径と連結度という二つの重要なパラメタを統合した概念であり、91年にD.F.Hsuによって明瞭な形で提案されたが、取り扱いが難しく、重要なわりに研究が進んでいない分野である。本論文では、kを自然数とするとき、k-diameterおよび(k-1)-fault diameterという2種類のwide diameterを扱っている。いずれもk＝1とすると通常の直径の概念に帰着する。

　論文提出者は以前Hanとの共著において、頂点数nとk-diameter(または(k-1)-fault diameter)dを指定したときのk連結グラフの辺の数の最大値を決定した。同じ状況における辺の数の最小値は、n2kという条件の下で、dがk-diameterの場合はk(n-k),dが(k-1)-fault diameterの場合は$113742f20.gif$になることが予想されるが、本論文では少し条件を課したときこの最小値が正しいことが示された。また頂点数nを指定したとき、k-regular k-connected graphのk-diameterの最大値に関して、94年にHsuおよびLuczakはkまたはnが偶数でk3のときこの最大値が高々$113742f21.gif$であることを示し、特にnが偶数2mの場合、最大値がちょうどmになる十分条件、mより真に小さくなる十分条件を求めた。特にこの十分条件は、k＝3の場合にはm2ならばこの最大値がちょうどmになることを含んでいる。論文提出者はこの考察をさらに推し進め、k＝4および5に対しては最大値がちょうど$113742f22.gif$になるための必要十分条件を求め、k6の場合に最大値がちょうど$113742f23.gif$になる十分条件、それより真に小さくなる十分条件を求めている。これらの結果は決定的なものではないが、将来につながる結果が得られているといえる。

　関連して、グラフGがvertex diameter criticalであるとは、Gのいかなる頂点に対しても、G-(Gから頂点およびから発するすべての辺を取り除いたグラフ)の直径がGの直径より真に大きくなることをいう。Boals,SherwaniおよびAliは90年に、vertex diameter critical graph Gに対して$113742f24.gif$が成立するという予想を提出した。この概念を拡張して、vertex k-diameter criticalという概念が定義できる。論文提出者は、k1かつn55k-14のとき、頂点数がnで辺の数が少なくとも$113742f25.gif$であるようなvertex k-diameter critical graphを構成した。これはk＝1とおくことにより、Boals-Sherwani-Aliの予想に対する反例になっている。また論文提出者はnがそれより小さい場合にも、辺の数がかなり大きいvertex k-diameter critical graphを実際に構成している。これはおもしろい構成で、例えばオーダーの最良性の評価など、今後の展開も期待される。

　第2部ではErdos-Sos予想に関連したtreeの埋め込みに関する問題を扱っている。Erdos-Sos予想とは、nおよびkを自然数とするとき、グラフGの頂点数がn,辺の数が少なくとも$113742f26.gif$であれば、k本の辺をもつ任意のtree TはGに埋め込むことができるという予想である。これに対しDobsonはグラフGとTに条件をつけた予想を提出した。すなわちtを自然数とし、$113742f27.gif$はGのgirthすなわちもっとも短いG中のcycleの長さ、(G)はGの頂点から出る辺の数の最小値、(T)はTの頂点から出る辺の数の最大値)という条件の下でErdos-Sos予想の結論が正しいと予想し、Brandtとともに96年にこのt＝2の場合をより弱い仮定のもとで証明し、それを用いてg(G)5の場合にErdos-Sos予想を証明した。論文提出者は、このDobsonの予想をt＝3かつk24の場合に証明した。もちろんtが一般の場合に証明できることが望ましいが、t＝3であってもその大部分の場合に正しいことがわかったことは興味深い。

　第3部ではグラフの三角形分解を論じている。グラフGが三角形分解可能であるとは、Gの辺全体の集合の集合としての分割であって、その各ブロックがGの3頂点を結ぶ三角形になっているようなものが存在することをいう。論文提出者は、まず任意の自然数tに対して(t1)(は頂点集合がt個ずつの3個のグループからなり、同一のグループに属する頂点の間には辺がなく、異なるグループに属する頂点の間にはすべて辺があるようなグラフ、以下同様),(tが2以上の偶数),(m≡1or3(mod6))が三角形分解可能であることを示した。一般にグラフGに関する性質P(G)があるとき、正整数の広義減少列d＝(d₁,d₂,…,d_n)がpotentially(resp.forcibly)P-graphicであるとは、degree sequence(グラフの各頂点から出る辺の数を多いほうから並べたもの)がdであるようなグラフが存在し、かつそのようなグラフのうちに性質Pをもつものが存在する(resp.そのようなグラフはすべて性質Pをもつ)ことをいう。論文提出者はd＝(p,p,…,p)の場合、すなわちグラフがp-regularの場合にPを三角形分解可能性としてこの問題を扱い、np+1,pが偶数、6|pnという自明な必要条件の下で、列(p,p,…,p)がpotentially P-graphicであること(すなわちこの条件の下で、頂点数がnの三角形分解可能なp-regular graphが存在すること)を構成的に示した。

　論文提出者は、以上の問題をすべてみずからのサーベイによって見つけ、全く独力でかなり緻密な考察によって興味深い結果を導いたものである。

　よって、論文提出者 張 忠良 は、博士(数理科学)の学位を受けるにふさわしい充分な資格があると認める。