不超过7阶的3-关系图的刻画

黄茹雅; 龙旸靖; 詹鹏锦

doi:10.19603/j.cnki.1000-1190.2024.02.001

华中师范大学学报（自然科学版） ›› 2024, Vol. 58 ›› Issue (02) : 159 -164. DOI: 10.19603/j.cnki.1000-1190.2024.02.001

不超过7阶的3-关系图的刻画

黄茹雅, 龙旸靖, 詹鹏锦

作者信息 +

Author information +

文章历史 +

摘要

给定一个图G,如果存在一个边标号树T,使得树T的叶子集等于图G的顶点集，并且树T任何叶子x到叶子y的唯一路径上的边标号之和为3当且仅当xy为图G的边，那么称图G是一个3-关系图.该文讨论了什么样的图是3-关系图，证明了图G是3-关系图的必要条件为图G是二部图，即只要图G包含奇圈，则图G不是3-关系图.更进一步，完全刻画了圈为3-关系图的充要条件，即一个圈是3-关系图当且仅当圈为偶圈，并且给出了偶圈相对应的边标号树.最后讨论了比较小的图为3-关系图的条件，即证明了阶至多为7的图是3-关系图的充分必要条件为图G是二部图.