k个拟传递有向图中的(k + 1)个核和k个国王的数目

时间:2024-04-06 05:34:28
【文件属性】:

文件名称:k个拟传递有向图中的(k + 1)个核和k个国王的数目

文件大小:494KB

文件格式:PDF

更新时间:2024-04-06 05:34:28

Quasi-transitive digraph; kk-quasi-transitive digraph; kk-king;

令D =(V(D),A(D))为有向图,k≥2为整数。 顶点x是D的k-king,如果对于每个y∈V(D),最多有一个k的(x,y)路径。 如果对于每对顶点u,v∈N,我们有d(u,v)≥k且d(v,u)≥k,则V(D)的子集N独立于k。 如果对于每个u∈V(D)-N,都存在v∈N使得d(u,v)≤l,则它是l吸收性的。 D的(k,l)内核是V(D)的k独立且l吸收的子集。 k内核是(k,k-1)内核。 如果对于长度为k的任何路径x0x1…xk,x0和xk相邻,则有向图D是k拟传递的。 最近,我们已经表明,当且仅当它具有唯一的初始强分量D1并且D1对扩展的(k + 1)周期不是同构的时,具有k≥4的k-拟传递有向图才具有k-king。 在本文中,我们将研究k-拟传递有向图中有k-king的k-king的数量。 的确,我们证明了当k = 4时,它可能恰好有一个4-king。 如果k≥5,则至少有两个k-king。 此外,我们在k个拟传递有向图中的(k + 1)-kings的最小数目上获得了新的结​​果。 Galeana-Sánchez等。 推测每个k-拟传递有向图都有(k + 1)个核。


网友评论