权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Upper bound graphとposetの関連について

关于上界图和偏序集之间的关系

基本信息

批准号：
07640332
负责人：
土屋守正
金额：
$ 1.41万
依托单位：
Tokai University
依托单位国家：
日本
项目类别：
Grant-in-Aid for General Scientific Research (C)
财政年份：
1995
资助国家：
日本
起止时间：
1995 至无数据
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-07640332/
关键词：
グラフ理論組合せ論交グラフ upper bound graph lower bound graph edge clique cover poset

项目摘要

Simplicial vertexの性質に注目することにより,グラフG及びGの補グラフGが共に,upper bound graphである為の特徴付けとしてGが次の(1),(2)の条件のいずれかを満たすsplite graphであることが得られた。ただし,V(G)=Ktsで,Kはcliquo,Sは独立集合である。(1)Kにsimplicial verlexが存在する。(2)Kの任意の辺e={u, v}に対して,u, v両方と隣接しているSの点心が存在し、Sの任意の2点x,yに対して,x, yの両方と隣接していないKの点心が存在する。Double bound graphに関しては,任意のグラフGに対して,Gを誘導部分グラフとして含むDouble bound graphが存在することがわかり,禁止部分グラフの言葉では,Double boand graphが特徴付けれないことがわかった。また連結な2部グラフGに対して,G,Eが共にDouble bound graphであることと,GがKm, nKm,-Ek, l, m, n, Ek, l-Er, sのいずれかであることが同値であることがわかった。ここで,Ek,lはGの辺部分集合で〈Ek,l〉_BがKk, lと同形なもののことであり,Km, nn-Ek, lは辺集合がE(Km, n)-Ek, lなる連結グラフ,Km, n-Ek, l-Er, sは辺集合がE(Km, n)-Ek, l-Er, sで,V(〈Ek, l〉_E)のV(〈Ec,s〉_E)=φなる連結グラフのことである。さらに,splite graph Gに関して,G ,Gが共にDouble bound graphであるための特徴付けや,極大元や極小元の集合のantichain性に注目することにより,strict Double bound graphの特徴付けを得た。posetからのアプローチにおいて,upper bound graphを特徴付けるclique coverがposetのcrder indealによるcoverに対応していることに注目し,upper bound graphが同形であるposet間の変換の特徴付けが得られた。またDouble bound graphについても同様の結果が得られた。simplicial vertex等のグラフ上の幾何学的性質を検討することにより,曲面上のLinear Arboricity to convex polygonへの分割に関する結果も得られている。

The property of simple vertex is the same as that of (1),(2), and the upper bound graph is the same as that of (1),(2).ただし,V(G)=Ktsで,Kはcliquo,Sは独立集合である。(1)K Simple verlex exists. (2)K Any pair of e={u, v} corresponds to u, v and K, and any pair of x, y corresponds to u, v and k exists. Double bound graph is related to, arbitrarily, G is related to, G is induced to.また链接な2部グラフGに対して,G,Eが共にDouble bound graphであることと,GがKm, nKm,-Ek, l, m, n, Ek, l-Er, sのいずれかであることが同値であることがわかった。ここで,Ek,lはGの辺部分集合で<Ek,l>_BがKk, lと同形なもののことであり,Km, nn-Ek, lは辺集合がE(Km, n)-Ek, lなる链接グラフ,Km, n-Ek, l-Er, sは辺集合がE(Km, n)-Ek, l-Er, sで,V(<Ek, l>_E)のV(<Ec,s>_E)=φなる链接グラフのことである。In addition, the split-graph G is related to G,G and G, and the characteristics of the double-bound graph are obtained. Poset's crder indeal is covered by the clip cover. Poset's crder indeal is covered Double bound graph is the result of a double bound graph. The geometric properties of simple vertex and so on are discussed, and the Linear Arboricity to convex polygon on the surface is discussed.