广义Petersen图的宽直径

广义Petersen图是一类重要的并被广泛研究的互连网络。本文证明了广义Petersen图 P(m,2)的直径和3宽直径分别为O(m/4)和O(m/3)。  

带弦圈的最小2宽直径

设k为正整数,G是简单k连通图.图G的k宽直径,dk(G),是指最小的整数ι使得对任意两不同顶点x,y∈V(G),都存在k条长至多为ι的内部不交的连接x和y的路.用C(n,t)表示在圈Gn上增加t条边所得的图.定义h(n,t):min{d2(C(n,t))}.本文给出了h(n,2)=[n/2].而且,给出了当t较大时h(n,t)的界.  

笛卡尔乘积图的成对控制

Let γpr（G） denote the paired domination number and G □ H denote the Cartesian product of graphs G and H. In this paper we show that for all graphs G and H without isolated vertex, γpr（G）γpr（H）≤ 7γpr （G □H）.  

由圈长分布确定的二部图~$K_{n,n r}-A\ (|A|\leq 3)$

The cycle length distribution of a graph G of order n is a sequence （c1 （G）,…, cn （G））, where ci （G） is the number of cycles of length i in G. In general, the graphs with cycle length distribution （c1（G） ,…,cn（G）） are not unique. A graph G is determined by its cycle length distribution if the graph with cycle length distribution （c1 （G）,…, cn （G）） is unique. Let Kn,n＋r be a complete bipartite graph and A lohtaib in E（Kn,n＋r）. In this paper, we obtain： Let s 〉 1 be an integer. （1） If r = 2s, n 〉 s（s - 1） ＋ 2｜A｜, then Kn,n＋r - A （A lohtain in E（Kn,n＋r）,｜A｜ ≤ 3） is determined by its cycle length distribution; （2） If r = 2s ＋ 1,n 〉 s^2 ＋ 2｜A｜, Kn,n＋r - A （A lohtain in E（Kn,n＋r）, ｜A｜ ≤3） is determined by its cycle length distribution.