完全图强乘积的强半径和强直径

首先证明2个非平凡完全图强乘积是完全图且具有强定向性,然后确定了完全图强乘积的最小强半径和最小强直径的精确值,给出了最大强直径和最大强半径的范围.最后通过利用强乘积的结合性,将上述结论推广到多个完全图的强乘积.

路和路的笛卡尔积的最小和最大定向强半径和强直径(英文)

强有向图D中任意两个点u,v的强距离sd(u,v)定义为D中包含u和v的最小有向强子图Duv的大小(弧的数目).D中一点u的强离心率se(u)定义为u到其他顶点的强距离的最大值.强有向图D的强半径srad(D)(相应的强直径sdiam(D))定义为D中所有顶点强离心率的最小值(相应的最大值).无向图G的最小定向强半径srad(G)(相应的最大定向强半径SRAD(G))定义为D中所有强定向的强半径的最小值(相应的最大值).无向图G的最小定向强直径sdiam(G)(相应的最大定向强直径SDIAM(G))定义为D中所有强定向的强直径的最小值(相应的最大值).本文确定了路和路的笛卡尔积的最小定向强半径srad(Pm×Pn)和强直径的值sdiam(Pm×Pn),给出了最大定向强半径SRAD(Pm×Pn)的界并提出关于最大定向强直径SDIAM(Pm×Pn)的一个猜想.

强定向图的k-强距离(英文)

对强连通有向图D的一个非空顶点子集S,D中包含S的具有最少弧数的强连通有向子图称为S的S teiner子图,S的强S teiner距离d(S)等于S的S teiner子图的弧数.如果S=k,那么d(S)称为S的k-强距离.对整数k 2和强有向图D的顶点v,v的k-强离心率sek(v)为D中所有包含v的k个顶点的子集的k-强距离的最大值.D中顶点的最小k-强离心率称为D的k-强半径,记为sradk(D),最大k-强离心率称为D的k-强直径,记为sd iamk(D).本文证明了,对于满足k+1 r,d n的任意整数r,d,存在顶点数为n的强竞赛图T′和T,″使得sradk(T)′=r和sd iamk(T)″=d;进而给出了强定向图的k-强直径的一个上界.

2顶点扩张图的最小强直径定向

给出了直径小于等于2的2顶点扩张图的最小强直径定向及一般的2顶点扩张图的最小的强直径的界,并且对直径大于等于3的树的2顶点扩张图也给出了最小强直径定向。

路与路强乘积的最小直径定向

给定一个无向图G,将G的每条边{xy}用弧xy或yx替代得到的有向图称为G的的定向图。使得G的所有定向图中直径最小的定向图称为G的最小直径定向。文章给出了两条路强乘积的最小直径定向。

圈的2顶点扩张图的最大强直径的一个下界

给定一个无向图G,将G的每条边{x,y}用弧xy或yx替代后得到的有向图称为G的定向图.若连通图G在定向后是强连通的,则称该定向为G的强定向.使得G的所有定向图中强直径最大的定向称为G的最大强直径定向.文章给出了n-圈(其中n≥3)的2顶点扩张图的最大强直径的一个下界.

Optimal Orientations of the Generalized Cycles

Optimal orientations of the generalized cycles are studied. For a graph G, let D（G） be the family of the strong orientations of G,d（G）=min {d（D） D∈D（G） and ρ（G）=d（G）-d（G）, whered（G） and d （D） are the diameters of G and D respectively. Evaluate the value of ρ（G） is evaluated by reduction to absurdity when G is a generalized cycle Cn [Km], and a complete result is obtained.

完全图字典乘积的强半径和强直径

目前针对乘积图的强距离研究已经取得丰富成果,主要给出完全图字典乘积的强距离结果.基于字典乘积图与其因子图的关系,确定了两个完全图字典乘积的最小强半径;利用因子图与字典乘积图的顶点数的关系,得到完全图字典乘积的最大强直径和最大强半径的范围.除此之外,通过字典乘积的结合性,将字典乘积图的相关强距离结果进一步推广到多个完全图的字典乘积.