共查询到20条相似文献,搜索用时 15 毫秒
1.
对于任意的正数M以及正整数d≥4,存在直径为d的i-边连通无环图G使得ζ(G)≥M,其中ζ(G)是G的Betti亏数,i=1,2,3。 相似文献
2.
最近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$ 可收缩边. 相似文献
4.
图的限制性边连通度等于其最小边度的一个充分条件 总被引:6,自引:1,他引:5
设G是有限简单无向图.D,g和δ分别表示G的直径,围长和顶点最小度,本文证明,如果D≤g-2,且δ≥3,那么λ'=ξ,这里λ'=λ'(G)和ξ=ξ(G)分别表示G的限制性边连通度和最小边度,它在条件和结论两个方面都改进了已有的研究结果。 相似文献
5.
6.
通过引进Mycielski图点集的一类特殊划分,利用该划分在Mycielski图循环着色中的特点改进了如下猜想:完全图的Mycielski图的循环色数等于它的点色数. 相似文献
7.
徐俊明 《高校应用数学学报(英文版)》1999,14(3)
Let G be a connected k(≥3)-regular graph with girth g. A set S of the edges in G is called an R2-edge-cut if G-S is disconnected and contains neither an isolated vertex nor a one-degree vertex. The R2-edge-connectivity of G, denoted by λ″(G), is the minimum cardinality over all R2-edge-cuts, which is an important measure for fault-tolerance of computer interconnection networks. In this paper, λ″(G)=g(2k-2) for any 2k-regular connected graph G(≠K5) that is either edge-transitive or vertex-transitive and g≥5 is given. 相似文献
8.
9.
10.
1 IntroductionLet G be a plane graph with the vertex set V(G), the edge set E(G), the faCe set F(G),and the maximum degree A(G). The edge-face chromatic number X.I (G) of G is the ndnimumnunther of colors assigned to E(G) U F(G) such that aliy two adjacent or incident elements havedifferent colors. By the definition, X.,(G) 2 A(G) is trivial. In 1975, MelnikovI4J raised thefollowing conjecture.,Coniecture 1.1 For every plane graph G, X.J (G) 5 A(G) 3.The conjecture has been ton… 相似文献
11.
吴举林 《高校应用数学学报(A辑)》1991,6(3):420-426
本文研究图的导出森林独立系统.在这个独立系统中,独立集是指导出子图不含圈的点子集.文中证明了图G的导出森林独立系统是拟阵当且仅当G是块森林.文中同时给出了在强弦图上求最大导出森林的多项式算法. 相似文献
12.
1.IntroductionAgraphG=(V,E)meansafinitegraphwithoutloopsandmultipleedgeswithvertexsetVandedgesetE,theclassicaledgeconnectivityA(G)ofGistheminimumsizeofasetUofedgessuchthatG--Uisdisconnected,andsuchasetUiscalledaoutsetofG.Notethatintheabovedefinition,absolutelynoconditionsorrestrictionsareimposedeitheronthecomponelltsofG--UoronthesetU.ThusitwouldseemnaturaltogeneralizetheconceptofedgeconnectivitybyintroducingsomeconditionsorrestrictionsonthecomponentsofG--Uand/orthesetU.Asageneralizatio… 相似文献
13.
结合边连通性,本文给出了一个图的Betti亏数由这个图的补图的着色数所确定的上界式,证明了所给出的上界式是最好的,得到关于图的最大亏格下界的若干新结果. 相似文献
15.
16.
本文研究了积图的点可区别均匀边染色问题.利用构造法得到了积图G×G的点可区别均匀边染色的一个结论,并且获得了等阶的完全图与完全图、星与星、轮与轮的积图的点可区别均匀边色数,验证了它们满足点可区别均匀边染色猜想(VDEECC). 相似文献
17.
18.
1IntroductionThesurfaceisacompact2-manifold.AnorientablesurfaCeofgenuskishomeonlorphictoaspherewithkhandles,whichwedenoteitbySk.Anon-orientablesurfaceofgenuskishomeomorphictoaspherewithkcrosscaps,whichwedenoteitbySa.AnembeddingMonsurfaceSgmeanstheunderlyinggraphofMisdrawnonSOsuchthatnoedgesintersecteachotherandeachfaceishomeomorphictothedisc[5],wedenoteitbyMCS,(orforS.).Irreduciblegraphscharacterizethosegraphswhichcannotbeembeddedonasurfacebutdeletinganyedgeofthisgraph,theresultantgraphc… 相似文献
19.
20.
Martin Lätsch 《Discrete Applied Mathematics》2008,156(17):3194-3202
As a generalization of directed and undirected graphs, Edmonds and Johnson [J. Edmonds, E.L. Johnson, Matching: A well-solved class of linear programs, in: R. Guy, H. Hanani, N. Sauer, J. Schönheim (Eds.), Combinatorial Structures and their Applications, Gordon and Breach, New York, 1970, pp. 88-92] introduced bidirected graphs. A bidirected graph is a graph each arc of which has either two positive end-vertices (tails), two negative end-vertices (heads), or one positive end-vertex (tail) and one negative end-vertex (head). We extend the notion of directed paths, distance, diameter and strong connectivity from directed to bidirected graphs and characterize those undirected graphs that allow a strongly connected bidirection. Considering the problem of finding the minimum diameter of all strongly connected bidirections of a given undirected graph, we generalize a result of Fomin et al. [F.V. Fomin, M. Matamala, E. Prisner, I. Rapaport, Bilateral orientations in graphs: Domination and AT-free classes, in: Proceedings of the Brazilian Symposium on Graphs, Algorithms and Combinatorics, GRACO 2001, in: Electronics Notes in Discrete Mathematics, vol. 7, Elsevier Science Publishers, 2001] about directed graphs and obtain an upper bound for the minimum diameter which depends on the minimum size of a dominating set and the number of bridges in the undirected graph. 相似文献