仙人掌图的m-步竞争数
The m-step competition number of cactus graphs
王晓怡 1邓波2
作者信息
- 1. 青海师范大学数学与统计学院,青海 西宁 810016
- 2. 青海师范大学数学与统计学院,青海 西宁 810016;藏语智能信息处理及应用国家重点实验室,青海西宁 810016
- 折叠
摘要
有向图D的m-步竞争图G是一个无向图,G与D具有相同的顶点集,若在G中顶点x和y相邻,当且仅当存在一个顶点a,在D中同时有从x到a和从y到a的长为m的有向路径.对于任意的无向图G,G与足够多的孤立顶点的并可以作为一个无圈有向图的m-步竞争图,则G的m-步竞争数是指满足条件的所添加的最小的孤立顶点的个数.本文主要研究了仙人掌图的m≥1-步竞争数.
Abstract
The m-step competition graph G of a digraph D with the same vertex set as D,satisfying that the verticesxand y in G are adjacent,if and only if there is a vertex a and two directed paths with length m from x to a and from y to a in D.For an undirected graph G,the union of G and some isolated vertices is an m-step competition graph of an acyclic digraph.The minimum number of isolated vertices added is called the m-step competition number of G.This paper mainly studied the m≥1-step competition number of cactus graphs.
关键词
有向图/竞争图/竞争数/仙人掌图Key words
digraph/competition graph/competition number/cactus graphs引用本文复制引用
基金项目
青海省创新平台建设项目(2022-ZJ-T02)
111工程(D20035)
国家自然科学基金项目(12261073)
出版年
2024
NETL
NSTL
万方数据