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

On families of partially ordered sets which have the common structure of upper or lower bounds and the character of graphs which represents them

关于具有上下界共同结构以及表示它们的图的特征的偏序集族

基本信息

批准号：
16540115
负责人：
ERA Hiroshi
金额：
$ 2.37万
依托单位：
BUNKYO University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2004
资助国家：
日本
起止时间：
2004 至 2005
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-16540115/
关键词：
Applied Mathematics Graph Theory Partially ordered set upper bound graph poset 離散数学組合せ論

项目摘要

In this research, we consider the characterizations of upper bound graphs of posets from various aspects. For a poset P, the upper bound graph of P is the graph G_p=(X,E), where an edge uv belongs to E iff there exists an element m of X such that m is an upper bound of u and v. F.R.McMorris and T.Zaslavsky show a characterization of upper bound graphs using the clique covering conception. Here we give different characterizations by constructive method and also by forbidden substructuresAn upper bound graph can be transformed into a nova by contractions and a nova can be transformed into an upper bound graph by splits. Where nova is a graph class obtained from a star K_<1.n> by replacing each edge with a complete graph with at least two edges. By these results, we get a characterization on upper bound graphs as follows.Let G be a connected graph. G is an upper bound graph if the graph obtained by successive contractions of adjacent non-simplicial vertices u and v satisfying the following conditions is a nova :(1)u and v are adjacent to a simplicial vertex of G.(2)there exist no pair of non-simplicial adjacent vertices x andy which are not adjacent to simlicial vertices of G satisfying ceirtain conditions.The second result is on the characterization of some restricted class of upper bound graphs by concept of forbidden subset in posets. For a poset P, a poset Q is an m-subposet of P iff (1)Q is a subposet of P and, (2)for any pair x,y of Q, x,y <=m for some m in P then there exists m' in Q with x,y <=m'. This definition is introduced by D.D.Scott in 1986. Using this concept we give the following results,(1)G is a split upper bound graph iff the canonical poset of G contain no poset P_<2K2> as an m-subposet.(2)G is a threshold upper bound graph iff the canonical poset of G contain no 2K_2 or P_w as m-subposets.(3)G is difference upper bound graph iff the canonical poset of G contain P_<2K2> or P^as m-subposets.where P_w and P^are certain elementary classes of posets.

在本研究中，我们从多个方面考虑了偏序集上界图的表征。对于偏置集P， P的上界图是图G_p=(X，E)，其中边uv属于E，如果存在X的元素m使得m是u和v的上界，则F.R.McMorris和T.Zaslavsky利用团覆盖概念给出了上界图的表征。这里我们用构造法和禁止子结构给出了不同的表征。上界图可以通过收缩转化为新星，新星可以通过分裂转化为上界图。其中nova是由恒星K_<1得到的图类。通过将每条边替换为至少有两条边的完全图，得到N >。根据这些结果，我们得到了上界图的如下表征。设G是连通图。如果满足以下条件的相邻非简单顶点u和v连续收缩得到的图是新星（nova）：(1)u和v与G的一个简单顶点相邻(2)不存在对非简单相邻顶点x和不与满足一定条件的G的相似顶点相邻的图，则G是上界图。第二个结果是利用偏集中禁止子集的概念刻画了一类受限的上界图。对于一个偏序集P，一个偏序集Q是P的m-传票集，如果(1)Q是P的m-传票集，(2)对于任意对x，y （Q, x,y <=m）对于P中的某个m，则存在m‘在Q中且x，y <=m’。这个定义是由D.D.Scott在1986年提出的。利用这一概念，我们得到了以下结果：(1)如果G的正则偏序集不包含偏序集P_<2K2>作为m-传讯集，则G是一个分裂上界图。(2)G是一个阈值上界图，如果G的正则序集不包含2K_2或P_w作为m个集。(3)G是差分上界图，如果G的正则序集包含P_<2K2>或P^作为m-传讯集。其中P_w和P^是偏序集的某些初等类。