3连通图的可去边数

设 e是 3连通图 G的一条边 ,如果 G- e是某个 3连通图的剖分 ,则称 e是 G的可去边 .本文给出了 3连通图的可去边数依赖于极大半轮的下界以及达到下界的极图 .     

3-连通3-正则图生成树外的可去边

G是3-连通图，e是G中的一条边．若G-e是3-连通图的一个剖分，则称e是3-连通图的可去边．否则，e是G中不可去边．本给出3-连通3-正则图中生成树外可去边的分布情况及数目．     

周长为3的m限制边割连通图

如果连通图的G存在边割S,使得G-S的每一个连通分支都含有至少m个顶点,则称图G是m限制边连通的.本文刻画了周长为3的m限制边连通图.     

最小次数至少为4的超欧拉图

设Ｇ是２－边－连通的ｎ阶图。假设对任何的的最小边割集Ｅ等于包含于Ｅ（Ｇ）且│Ｅ│≤３,Ｇ－Ｅ的每个分支的阶至少为ｎ／５,则或者Ｇ是一个超欧拉图或者Ｇ有５个互不相交的阶数为ｎ／５连通分支,当这５个分支都收缩时,Ｇ收缩为Ｋ２,３,这个结果推广了蔡小涛,Ｐ．Ａ．Ｃａｔｌｉｎ,Ｆ．Ｊａｅｇｅｒ和Ｈ．Ｊ．Ｌａｉ等人关于超欧拉图的结果。     

3连通平面图的可去边数

设e是3连通图G的一边。如果G-e是某个3连通图的剖分,则称e是G的可去边。用v表示G的顶点数,本文证明了当v≥6时,3连通平面图G的可去边数的下界是v+4/2,此下界是可以达到的。     

一类泛连通无爪图

本文证明了如果Ｇ是３连通无爪图，且Ｇ的每个导出子图Ａ，Ａ＋都满足（ａ１，ａ２），则Ｇ是泛连通图（除了当ｕ，ｖ∈Ｖ（Ｇ），ｄ（ｕ，ｖ）＝１时，Ｇ中可能不存在（ｕ，ｖ）－ｋ路外，这里２≤ｋ≤４）．     

恰有k条非基本边的极小3连通图

设G是简单3连通图．G\e(删除边e)和G/e(收缩边e)都不是简单3连通图,则e称为G的基本边．对于3连通图中的非基本边．Tutte证明了：唯一没有非基本边的简单3连通图是轮．Oxley和Wu确定了至多有3条非基本边的所有极小3连通图以及恰有4条非基本的极小3连通图．Reid与Wu确定了至多有5条非基本边的极小3连通图．在本文中,我们在极小3连通图中定义了三种运算,然后通过轮利用这些运算的逆运算给出恰有k(k■2)条非基本边的极小3连通图的一种构造方法．     

周长为4不含3圈的m限制边连通图

m限制边割是连通图的一个边割,它将此图分离成阶不小于m的连通分支刻画了周长为4,不含3圈的m限制边割的图类.     

Cayley图的边Hamilton性

设Ｘ是有限群Ｇ的一个生成集．Ｃａｙ（Ｘ：Ｇ）表示生成集为Ｘ的Ｇ上的Ｃａｒｌｅｙ图，其顶点集为Ｇ，其边集为所有无序对［ａ，ｂ］组成的集合，其中ａ，ｂ∈Ｇ，ａ－１ｂ∈Ｘ∪Ｘ－１（Ｘ－１＝｛ｘ－１｜ｘ∈Ｘ｝）．若图的每条边都在的Ｈａｍｉｌｔｏｎ圈上，则称图是边－Ｈａｍｉｌｔｏｎ图．本文证明了：当Ｇ为ｐ－群或Ｈａｍｉｌｔｏｎ群时，若Ｘ含有Ｇ的中心元，则Ｃａｙ（Ｘ：Ｇ）是边－Ｈａｍｉｌｔｏｎ图．     

关于图的定向4—边形嵌入

本文中考虑的图均是连通的．没有重边和环的图称为简单的．若Ｘ为一个图Ｇ的边子集,记号 Ｇ＼表示 Ｇ中去掉 Ｘ中的所有边后所得到的图．有关图的基本术语和记号均同［１］．Ｐｉｓａｎｋｉ在［２］中研究正则偶图的定向４－边形嵌入．所谓一个图Ｇ的定向４－边形嵌入是指Ｇ到某定向曲面Ｓ的一个２－胞腔嵌入使得Ｇ在Ｓ上的每个面的边界是Ｇ中一个长为４的圈（这里,Ｇ中的圈是Ｇ的一条点不交的闭迹）．若Ｇ为简单偶图,因Ｇ中不含长为１,２和３的圈,由Ｅｕｌｅｒ公式确定Ｇ有定向４－边形嵌入等价确定了Ｇ的最小亏格嵌入．关于这类问题…     

EDGE-FACE CHROMATIC NUMBER OF 2-CONNECTED PLANE GRAPHS WITH HIGH MAXIMUM DEGREE

The edge-face chromatic number Xef (G) of a plane graph G is the least number of colors assigned to the edges and faces such that every adjacent or incident pair of them receives different colors. In this article, the authors prove that every 2-connected plane graph G with△(G)≥|G| -2△9 has Xef(G)=△(G).     

Removable Edges in Longest Cycles of 4-Connected Graphs

Let G be a 4-connected graph. For an edge e of G, we do the following operations on G: first, delete the edge e from G, resulting the graph G–e; second, for all vertices x of degree 3 in G–e, delete x from G–e and then completely connect the 3 neighbors of x by a triangle. If multiple edges occur, we use single edges to replace them. The final resultant graph is denoted by Ge. If Ge is 4-connected, then e is called a removable edge of G. In this paper we obtain some results on removable edges in a longest cycle of a 4-connected graph G. We also show that for a 4-connected graph G of minimum degree at least 5 or girth at least 4, any edge of G is removable or contractible.Acknowledgment. The authors are greatly indebted to a referee for his valuable suggestions and comments, which are very helpful to improve the proof of our main result Lemma 3.3.Research supported by National Science Foundation of China AMS subject classification (2000): 05C40, 05C38, 05C75Final version received: March 10, 2004     

5连通图中的可去边

An edge e of a k-connected graph G is said to be a removable edge if G O e is still k-connected, where G e denotes the graph obtained from G by deleting e to get G - e, and for any end vertex of e with degree k - 1 in G- e, say x, delete x, and then add edges between any pair of non-adjacent vertices in NG-e （x）. The existence of removable edges of k-connected graphs and some properties of 3-connected and 4-connected graphs have been investigated [1, 11, 14, 15]. In the present paper, we investigate some properties of 5-connected graphs and study the distribution of removable edges on a cycle and a spanning tree in a 5- connected graph. Based on the properties, we proved that for a 5-connected graph G of order at least 10, if the edge-vertex-atom of G contains at least three vertices, then G has at least （3│G│ ＋ 2）/2 removable edges.     

不含某些子图的k连通图中的k可收缩边

最近Ando等证明了在一个$k$($k\geq 5$ 是一个整数) 连通图 $G$ 中,如果 $\delta(G)\geq k+1$, 并且 $G$ 中既不含 $K^{-}_{5}$,也不含 $5K_{1}+P_{3}$, 则$G$ 中含有一条 $k$ 可收缩边.对此进行了推广,证明了在一个$k$连通图$G$中,如果 $\delta(G)\geq k+1$,并且 $G$ 中既不含$K_{2}+(\lfloor\frac{k-1}{2}\rfloor K_{1}\cup P_{3})$,也不含 $tK_{1}+P_{3}$ ($k,t$都是整数,且$t\geq 3$),则当 $k\geq 4t-7$ 时, $G$ 中含有一条 $k$ 可收缩边.     

无C_4图的邻域同调分类

本文证明了两个连通的无C4图是邻域同调的充要条件为它们的二分性相同，并且圈秩相等．     

一些积图的点可区别均匀边色数

本文研究了积图的点可区别均匀边染色问题.利用构造法得到了积图G×G的点可区别均匀边染色的一个结论,并且获得了等阶的完全图与完全图、星与星、轮与轮的积图的点可区别均匀边色数,验证了它们满足点可区别均匀边染色猜想(VDEECC).     

对称群上的一类Cayley图的边传递性和Hamilton性

Let Sn be the symmetric group,g+I=(123i),g-I=(1i32) and M+n={g+I:4≤I≤n},then M+n is a minimal generating set of Sn,where n≥5.It is proved that Cayley graph Cay(Sn,M+n∪M-n) is Hamiltonian and edge symmetric.