n重线有向图的超连通性

本文证明了，在最小度至少为3的前提下超弧连通有向图的迭代线图是超点连通的．作为推论，我们得到了Kautz网络和de Bruijn网络的超点连通性和超弧连通性．     

有向Cayley图的直径

设Ｇ是一个有限Ａｂｅｌ群，Ｍ是Ｇ的一个二元生成集．Ｇ上的有向Ｃａｙｌｅｙ图Ｄ（Ｃ，Ｍ）是一个以Ｇ为顶点集的有向图，若ｘ，ｙ∈Ｇ，则存在ｘ到ｙ的弧当且仅当ｙ－ｘ∈Ｍ．Ｎ个顶点的所有这种有向Ｃａｙｌｅｙ图的最小直径和平均距离是多少？我们将此问题转化为一个几何问题并由此得到了直径的一个下－２和平均距离的一个下界．这两个界仅当Ｎ＝３ｘ２时可达，这里ｘ是任一自然数．     

论abc—三次图

G.Malle在《论最大二部分子图》一文中提出了关于abc—三次图的一些问题,他指出了111—三次图是连通二部分三次图,并证明了不含三角形的图是222—三次图的充要条件是图为彼得松图或十二面体图,他还指出,对其它abc—三次图的特征是尚未解决的问题。本文解决了在“无三角形”限制下abc—三次图的存在性及最小图,以及不加任何限制的abc—三次图的存在性及最小图。本文及我们的[5][6][7]三文基本上解决了G.Malle提出的问题,同时也证实了他关于“可能某些abc—三次图不存在”的说法, 一、无三角形abc—三次图的存在性及最小图本文使用[1]及[2]的有关术语及记号。图G的子图H称为G的最大二部分子图,若对G的任意二部分子图H′,都有ε(H′)≤ε(H),这里ε表示图的棱数。     

无限图的笛卡尔积的哈密顿性和连通性

本文证明了两个连通有向或无向图(至少有一个无限)的笛卡尔积的连通度不小于它们的连通度之和,并讨论了一些特殊图的笛卡尔积的哈密顿分解及哈密顿性。     

上连通和超连通的三次Bi-Cayley图

Let G be a finite group and let S(possibly, contains the identity element) be a subset of G. The Bi-Cayley graph BC(G, S) is a bipartite graph with vertex set G×{0, 1} and edge set {(g, 0) (sg, 1) : g∈G, s ∈ S}. A graph is said to be super-connected if every minimum vertex cut isolates a vertex. A graph is said to be hyper-connected if every minimum vertex cut creates two components, one of which is an isolated vertex. In this paper, super-connected and/or hyper-connected cubic Bi-Cayley graphs are characterized.     

两类Cayley图的Hamilton性

域Ｆ上的所有ｍ×ｎ矩阵记为Ｆ（ｍ×ｎ），域Ｆ上的所有ｎ×ｎ可逆矩阵构成的乘群，称为一般线性群，记为ＧＬｎ（Ｆ），当Ｆ是无限可列数域时，本文证明了Ｆ（ｍ×ｎ）和ＧＬｎ（Ｆ）上的连通Ｃａｙｌｅｙ图是无限连通的，从而可Ｈａｍｉｌｔｏｎ分解．     

太阳图与路的笛卡儿积图的任意可分性（英文）

一个阶为n的图G称为是任意可分的(简作AP),如果对于任一正整数序列τ=(n₁,n₂,…,n_k)满足n=n₁+n₂+…+n_k,总是存在顶点集V(G)的一个划分(V₁,V₂,…,V_k)满足:对于i∈[1,k],|V_i|=n_i,且子图G|V_i|是图G的V_i导出的一个连通子图.我们用S~*=S(n;m₁,m₂,…,m_n)来表示最大度△(S~*)=3的太阳图.本文讨论了图S~*P_m(m≥3)的任意可分性.     

上连通和超连通三次点传递图(英)

图G称为上连通的,若对每个最小割集C,G-C有孤立点.G称为超连通的,若对每个最小割集G,G-C恰有两个连通分支,且其中之一为孤立点.本文刻划了上连通和超连通三次点传递图.     

由对换树生成的凯莱图的3-额外连通度

给定一个图G和一个非负整数g,若图G中存在(边)点集,使得删除该集合后图G不连通并且每个连通分支的点数大于g,所有这样的(边)点集的最小基数,称为g-额外(边)连通度(记作κg(G)(λg(G)).本文将确定由对换树生成的凯莱图的3-额外(边)连通度(记作κ3(λ3).     

阶为奇且连通的双环网络的书式嵌入

嵌入阶为奇的双环网络.图G的书式嵌入包括把G的顶点放置到书脊上并且分配图!G的到书页上且保证每个书页上无相交的边.