图的最大亏格与2-因子

图Ｇ的一个２因子Ｆ就是Ｇ的这样一个支撑子图，使其任何节点ｖ∈Ｖ的次ｄＦ（ｖ）＝２．易见，Ｇ的每个２因子均为无公共节点的圈之并．若Ｆ的每个圈的长均为３（或４），则称Ｇ含有一个三角形（或四边形）２因子．Ｍ．ｋ∨ｏｖｉｅｒａ［５］得到了含有三角形２因子的３－正则图的最大亏格．本文在３－正则图上，引进了扩张运算和讨论了与最大亏格和Ｂｅｔｉ亏数之间的关系．利用这些运算，得到了所有含四边形２因子的连通３－正则图是上可嵌入的，即γＭ（Ｇ）＝ｎ４（ｎ为Ｇ的节点数ｎ＝｜Ｖ（Ｇ）｜）．然后，基于此证明了含四边形２因子且所有节点ｖ∈Ｖ的次ｄＧ（ｖ）＝３（ｍｏｄ４）的图Ｇ均为上可嵌入的     

关于3正则图的三匹配交猜想（I）

Fan和Raspaud1994年提出如下猜想：任一无桥3正则图必有三个交为空集的完美匹配。本研究一类特殊的无桥3正则图G：存在图的G的一个完美匹配M1使得G－M1恰含有两个奇圈和若干偶圈。在偶圈数≤2的情形以及在偶圈数≤4且G是圈4－边连通的情形，本证明了一定存在图G的两个完善匹配M2和M3使得M1∩M2∩M3＝φ。     

图的最大亏格的一个性质

本文所考虑的图均指有限元向图，没有解释的术语和记号同[1]．一个图称为简单图如果不含重边及环．曲面S这里指一个紧的，连通的，2－维闭流形（定向或不可定向），其亏格记为g（S）．连通图G在曲面S上的一个2－胞腔嵌入意指存在一个1－1连续映射h：G→S使得S＼h（G）的每个连通分支与圆盘拓扑同胚．连通图G的定向亏格γ（G）（或不可定向亏格γ（G））是指最小的整数k使得G在亏格为k的定向（或不可走向）曲面S上有2－胞腔嵌入；而图G的最大定向亏格，也常称之为最大亏格，记为γM（G）,是指最大的整数k使得G在亏格为k定向曲面S上有…     

加边与删边运算下图的亏格分布

设(G,u,v)是以u和u为根的双根连通图,用边e连接点u和v,所得之图记为G+E.Gross对根u和v的度均为2的情形,给出了G+e的亏格分布与(G,u,v)的部分亏格分布之间的一个关系.本文推广到有一个根的度可以任意大的情形,并由(G,u,v)的部分亏格分布导出了G+e的亏格分布.     

一类完全三部图的K1,3-因子大集

令G是一个有限图,H是G的一个子图.若V(H)=V(G),则称H为G的生成子图.图G的一个λ重F-因子,记为Sλ(F,G),是G的一个生成子图且可分拆为若干与F同构的子图(称为F-区组)的并,使得V(G)中的每一个顶点恰出现在λ个F-区组中.一个图G的λ重F-因子大集,记为LSλ(F G),是G中所有与F同构的子图的一个分拆{B_i}_i,使得每个B_i均构成一个Sλ(F,G).当λ=1时,λ可省略不写.本文中,我们证明了当v≡4 mod 24时,存在LS(K1,3,Kv,v,v).     

最大匹配数的一个问题

一、本文仅讨论简单图。图G的1-因子数记为F(G)。 f(G)记使如下事实正确的最大的K:“假如G是一个n-连通图且G有1-因子,则G至少有k个1-因子”。包含G的所有的点,且每个点的度为0或1的G的子图叫G的一个匹配M,有最大的边数的匹配称为最大匹配。假如匹配M的一个点v的度为0,称v为在M里的分离点。以M(G)表示G的最大匹配的集合。假如图G的一个点v所关连的每一条边都属于G的一个最大匹配,称点v被M(G)完全覆盖。     

一类正则循环图的Cartesian积图的D(β)-点可区别VI-全染色及I-全染色

设G是简单图,若图G的全染色f满足:1)(?)uv,vw∈E(G),有f(uv)≠f(vw);2)(?)uv∈E(G),u≠v,有f(u)≠f(v);3)(?)u,v∈V(G),0相似文献   

平面图的(3,1)~*-可选择性

若对图G的任何一个满足|L(v)|=k的列表配置L,存在G的一个L-染色c使G的每个顶点v至多有d个邻点和v染相同的颜色,则称图G是(k,d)~*-可选的.本文证明了:(1)若G是i-圈和j-圈(i,j∈{3,4})不相交的平面图,则G是(3,1)~*-可选的.(2)不含6圈和相交3-圈的平面图是(3,1)~*-可选的.     

关于连通度的无三圈图的划分（英文）

Kühn和Osthus证明了对每个正整数l,都存在一个整数k(l)≤2~(16)l~2,使得每个k(l)-连通图G的顶点集都可以划分成两个子集S,T满足G[S],G[T]都是l-连通的,且S中的每个点在T中都有l个邻点.本文主要考虑无三圈图的划分问题,主要关注连通度k(l)的上界.通过证明每个平均度至少为8l/3的无三圈图都存在一个l-连图子图,我们证明了对无三圈图,k(l)≤2~(16)·3~(-3)l~2.     

两类完全三部图的图因子大集

令G是一个有限图,H是G的一个子图.若V(H)=V(G),则称H为G的生成子图.图G的一个λ重F-因子,记为S_λ(F,G),是G的一个生成子图且可分拆为若干与F同构的子图(称为F-区组)的并,使得V(G)中的每一个顶点恰出现在λ个F-区组中.一个图G的λ重F-因子大集,记为LS_λ(F,G),是G中所有与F同构的子图的一个分拆{B_i},使得每个B_i均构成一个S_λ(F,G).当λ=1时,λ可省略不写.在[Ars Combin.,2010,96:321-329]中已经得到了LS_λ(K_(1,2),K_(v,v))的存在谱.本文证明了当v≡4(mod 12)时,存在LS(F,K_(v,v,v)),这里F∈{K_(1,3),K_(2,2)}.     

On 2-factor hamiltonian regular bipartite graphs

A k-regular bipartite graph is said to be 2-factor hamiltonian if each of its 2-factor is hamiltonian. It is well known that if a k-regular bipartite graph is 2-factor hamiltonian, then k?Q3. In this paper, we give a new proof of this fact.     

Tutte's 5-flow conjecture for graphs of nonorientable genus 5

We develop four constructions for nowhere-zero 5-flows of 3-regular graphs that satisfy special structural conditions. Using these constructions we show a minimal counter-example to Tutte's 5-Flow Conjecture is of order ≥44 and therefore every bridgeless graph of nonorientable genus ≤5 has a nowhere-zero 5-flow. One of the structural properties is formulated in terms of the structure of the multigraph G(F) obtained from a given 3-regular graph G by contracting the cycles of a 2-factor F in G. © 1996 John Wiley & Sons, Inc.     

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

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

Non-separating 2-factors of an even-regular graph

For a 2-factor F of a connected graph G, we consider G−F, which is the graph obtained from G by removing all the edges of F. If G−F is connected, F is said to be a non-separating 2-factor. In this paper we study a sufficient condition for a 2r-regular connected graph G to have such a 2-factor. As a result, we show that a 2r-regular connected graph G has a non-separating 2-factor whenever the number of vertices of G does not exceed 2r²+r.     

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-因子的并.     

2-边连通图的线图的P3因子

如果图G有一个生成子图使得这个生成子图的每一个分支都是3个点的路，则称G有P3-因子．本文证明了对任何一个2-边连通图G，只要G的边数能被3整除，则G的线图就有P3-因子。     

Decomposition of cubic graphs with a 2-factor consisting of three cycles

The 3-Decomposition Conjecture states that every connected cubic graph can be decomposed into a spanning tree, a 2-regular subgraph and a matching. We prove that this conjecture is true for connected cubic graphs with a 2-factor consisting of three cycles.     

一类3-正则图的邻强边染色

对简单图G(V,E),f是从V(G)∪E(G)到{1,2,…,k}的映射,k是自然数,若f满足(1)uv,uw∈E(G),u≠w,f(uv)≠f(uw);(2)uv∈E(G),C(u)≠C(v).则称f是G的一个邻强边染色,最小的k称为邻强边色数,其中C(u)={f(uv)|uv∈E(G)}.给出了一类3-正则重圈图的邻强边色数.     

The genus distributions for a certain type of permutation graphs in orientable surfaces

A circuit is a connected nontrivial 2-regular graph.A graph G is a permutation graph over a circuit C,if G can be obtained from two copies of C by joining these two copies with a perfect matching.In this paper,based on the joint tree method introduced by Liu,the genus polynomials for a certain type of permutation graphs in orientable surfaces are given.     

<Emphasis Type="Italic">k</Emphasis>-factors in regular graphs

Plesnik in 1972 proved that an （m - 1）-edge connected m-regular graph of even order has a 1-factor containing any given edge and has another 1-factor excluding any given m - 1 edges. Alder et al. in 1999 showed that if G is a regular （2n ＋ 1）-edge-connected bipartite graph, then G has a 1-factor containing any given edge and excluding any given matching of size n. In this paper we obtain some sufficient conditions related to the edge-connectivity for an n-regular graph to have a k-factor containing a set of edges and （or） excluding a set of edges, where 1 ≤ k ≤n/2. In particular, we generalize Plesnik＇s result and the results obtained by Liu et al. in 1998, and improve Katerinis＇ result obtained 1993. Furthermore, we show that the results in this paper are the best possible.