广义Petersen图的宽直径

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

关于广义Petersen图的紧致性的注记

We show that, for each integer n ≥ 5, the toughness of a generalized Petersen graph with 2n vertices is less than or equal to 4/3, and 4/3 is the best upper bound.     

广义Petersen图的弱点传递性

图X称为弱点传递图如果X的自同态幺半群EndX在顶点集V(X)上的作用是传递的 .本文给出了广义Petersen图是二分图的充要条件 ,刻划了奇围长小于 9的广义Petersen图的弱点传递性 ,作为推论给出了所有h ≤ 1 5的弱点传递的广义Pe tersen图P(h ,t) .     

两类四正则图的完全亏格分布

一个图G的完全亏格多项式表征了图G的亏格(可定向,不可定向)分布情况.本文利用刘彦佩提出的嵌入的联树模型,得出了两类新的四正则图的完全亏格多项式,并推导出已有结果的两类图的完全亏格多项式.此处的结果形式更为简单.     

G(2m+1,m)的不可定向强最大亏格

图G的最大亏格指图G能嵌入到亏格为k的曲面的最大整数k.对于广义Petersen图G(2m 1,m),当m=1,4(mod 6),给出了最大亏格的表达式,对其余形,给出了不可定向强最大亏格的上界和下界.     

广义Petersen图的宽直径

Generalized Petersen graphs are commonly used interconnection networks,and wide diameter is an important parameter to measure fault-tolerance and efficiency of parallel pro- cessing computer networks.In this paper,we show that the diameter and 3-wide diameter of generalized Petersen graph P (m,a) are both O( m 2a ),where a ≥ 3.     

一般梯图的亏格分布

本文求出了-些曲面集的亏格分布的显式表达式.在联树的基础上,通过运用曲面分类法把一般梯图的亏格分布转化为这些曲面集的线性组合,从而可求出它们的显式表达式.     

Petersen图的Hamilton性和边色数

对简单图G(V,E),定义图G的关联图I(G)为V(I(G))={(ve)|v∈V(G)且e∈E(G)和v与e关联},E(I(G))={(ue,vf)Iu=v或e=f或uv=e或uv=f}.本文证明了Petersen图可被分解为边不交的Hamilton-圈和一个1-因子的并.     

一类图的亏格

在刘提出的联树模型的基础上,更广泛未必具有对称性的图类的亏格问题可以得到解决．本文中,我们得到了一类具有比较弱对称性的新图类的亏格．作为推论亦得到了完全三部图Kn,n,l（l≥n≥2）的亏格．此处所用方法比已知用来计算图的亏格问题的方法,如电流图等,更直接且可用线性时间算法实现．     

两类花束图的部分对偶欧拉亏格多项式

[European J.Combin.,2020,86:Paper No.103084,20 pp.]在带子图中引入了部分对偶欧拉亏格多项式的概念,并给出插值猜想,即任意不可定向带子图的部分对偶欧拉亏格多项式是插值的.[European J.Combin.,2022,102:Paper No.103493,7 pp.]给出了两类反例否定了插值猜想,这两类花束图含有的侧面环只有一条或者两条不可定向环.本文是在[European J.Combin.,2022,102:Paper No.103493,7 pp.]的基础上,进一步计算其它两类花束图的部分对偶欧拉亏格多项式,其中一类是非插值的,它的侧面环有任意条不可定向环;而另一类是插值的,它的侧面环有任意条可定向环和不可定向环.     

Embedding Generalized Petersen Graph in Books

A book embedding of a graph $G$ consists of placing the vertices of $G$ on a spine and assigning edges of the graph to pages so that edges in the same page do not cross each other. The page number is a measure of the quality of a book embedding which is the minimum number of pages in which the graph $G$ can be embedded. In this paper, the authors discuss the embedding of the generalized Petersen graph and determine that the page number of the generalized Petersen graph is three in some situations, which is best possible.     

Jacobsthal Numbers in Generalized Petersen Graphs

We prove that the number of 1‐factorizations of a generalized Petersen graph of the type is equal to the kth Jacobsthal number when k is odd, and equal to when k is even. Moreover, we verify the list coloring conjecture for .     

On the Hamilton connectivity of generalized Petersen graphs

We investigate the Hamilton connectivity and Hamilton laceability of generalized Petersen graphs whose internal edges have jump 1, 2 or 3.     

广义彼得森图的2—可扩性

本文证明了当k≥3,n≠2k,3k时,广义彼得森图GP(n,k)中的任意两条不邻接边都包含在GP(n,k)的1-因子中。     

The exact domination number of the generalized Petersen graphs

Let G=(V,E) be a graph. A subset S⊆V is a dominating set of G, if every vertex u∈V−S is dominated by some vertex v∈S. The domination number, denoted by γ(G), is the minimum cardinality of a dominating set. For the generalized Petersen graph G(n), Behzad et al. [A. Behzad, M. Behzad, C.E. Praeger, On the domination number of the generalized Petersen graphs, Discrete Mathematics 308 (2008) 603-610] proved that and conjectured that the upper bound is the exact domination number. In this paper we prove this conjecture.