共查询到20条相似文献,搜索用时 373 毫秒
1.
图的最大亏格与2-因子 总被引:13,自引:0,他引:13
图G的一个2因子F就是G的这样一个支撑子图,使其任何节点v∈V的次dF(v)=2.易见,G的每个2因子均为无公共节点的圈之并.若F的每个圈的长均为3(或4),则称G含有一个三角形(或四边形)2因子.M.k∨oviera[5]得到了含有三角形2因子的3-正则图的最大亏格.本文在3-正则图上,引进了扩张运算和讨论了与最大亏格和Beti亏数之间的关系.利用这些运算,得到了所有含四边形2因子的连通3-正则图是上可嵌入的,即γM(G)=n4(n为G的节点数n=|V(G)|).然后,基于此证明了含四边形2因子且所有节点v∈V的次dG(v)=3(mod4)的图G均为上可嵌入的 相似文献
2.
Fan和Raspaud1994年提出如下猜想:任一无桥3正则图必有三个交为空集的完美匹配。本研究一类特殊的无桥3正则图G:存在图的G的一个完美匹配M1使得G-M1恰含有两个奇圈和若干偶圈。在偶圈数≤2的情形以及在偶圈数≤4且G是圈4-边连通的情形,本证明了一定存在图G的两个完善匹配M2和M3使得M1∩M2∩M3=φ。 相似文献
3.
图的最大亏格的一个性质 总被引:2,自引:0,他引:2
本文所考虑的图均指有限元向图,没有解释的术语和记号同[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上有… 相似文献
4.
设(G,u,v)是以u和u为根的双根连通图,用边e连接点u和v,所得之图记为G+E.Gross对根u和v的度均为2的情形,给出了G+e的亏格分布与(G,u,v)的部分亏格分布之间的一个关系.本文推广到有一个根的度可以任意大的情形,并由(G,u,v)的部分亏格分布导出了G+e的亏格分布. 相似文献
5.
令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). 相似文献
6.
一、本文仅讨论简单图。图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)完全覆盖。 相似文献
7.
《数学的实践与认识》2013,(7)
设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相似文献
8.
9.
10.
《数学进展》2017,(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)}. 相似文献
11.
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. 相似文献
12.
Eckhard Steffen 《Journal of Graph Theory》1996,22(4):309-319
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. 相似文献
13.
两类四正则图的完全亏格分布 总被引:3,自引:2,他引:1
一个图G的完全亏格多项式表征了图G的亏格(可定向,不可定向)分布情况.本文利用刘彦佩提出的嵌入的联树模型,得出了两类新的四正则图的完全亏格多项式,并推导出已有结果的两类图的完全亏格多项式.此处的结果形式更为简单. 相似文献
14.
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 2r2+r. 相似文献
15.
16.
如果图G有一个生成子图使得这个生成子图的每一个分支都是3个点的路,则称G有P3-因子.本文证明了对任何一个2-边连通图G,只要G的边数能被3整除,则G的线图就有P3-因子。 相似文献
17.
《Discrete Mathematics》2020,343(6):111839
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. 相似文献
18.
对简单图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-正则重圈图的邻强边色数. 相似文献
19.
The genus distributions for a certain type of permutation graphs in orientable surfaces 总被引:1,自引:0,他引:1
Rong-xia HAO~ 《中国科学A辑(英文版)》2007,50(12):1748-1754
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. 相似文献
20.
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. 相似文献