抄録/ポイント:
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
グラフGの横方向集合は,Gのすべてのエッジに入射する頂点の集合である。τ(G)によって表示されたGの横数は,Gの横方向集合の最小基数である。分離した頂点のない簡単なグラフGは,τ(G-e)<τ(G)があらゆるエッジe>E(G)に対してτ臨界と呼ばれる。τ(G)=tを有する任意のτ臨界グラフGに対して,Erd HosとGallaiによる|V(G)|>2tと|E(G)|t+1がErd Hos,HajnalとMoonによって2を選択することを示した。最近,それは,Gy’arf’asとLelelが|V(G)|+|E(G)|t+2選択2に拡張された。本論文では,スペクトルにより強い結果を証明した。Gはτ(G)=tと|V(G)|=nのτ臨界グラフであり,letλ_1はGの隣接行列の最大固有値を示す。著者らは,もしGがtK_2,K_s+1∪(t-s)K_2,またはC_2s-1∪(t-s)K_2,ここで2≦s≦tであるならば,同等性を有するn+λ_1≦2t+1を示した。特に,GがK_t+1である場合のみ,同等性でλ_1(G)≦tであった。次に,任意の非負整数rに対して,n(r+λ_1/2)≦t+r+1を選択し,全ての極値グラフを特徴付けることを示した。これは,r|V(G)|+|E(G)|Δt+r+1が2を選ぶ純粋な組合せ結果を意味し,それはErd H{o}s-Hajnal-Moon定理とGy’arf’as-Lehel定理より強かった。また,いくつかの他の一般化がある。【JST・京大機械翻訳】