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

黄茹雅, 龙旸靖, 詹鹏锦

华中师范大学学报(自然科学版) ›› 2024, Vol. 58 ›› Issue (02) : 159 -164.

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

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

    黄茹雅, 龙旸靖, 詹鹏锦
作者信息 +

Author information +
文章历史 +
PDF

摘要

给定一个图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是二部图.

关键词

3-关系图 / 边标号树 / / 二部图

Key words

引用本文

引用格式 ▾
不超过7阶的3-关系图的刻画[J]. 华中师范大学学报(自然科学版), 2024, 58(02): 159-164 DOI:10.19603/j.cnki.1000-1190.2024.02.001

登录浏览全文

4963

注册一个新账户 忘记密码

参考文献

AI Summary AI Mindmap
PDF

72

访问

0

被引

详细

导航
相关文章

AI思维导图

/