共查询到19条相似文献,搜索用时 437 毫秒
1.
设G是一个图,其边集是E(G),E(G)是一个子集S称为G的一个边覆盖,若G是每一点都是S中一条边的端点,G的一个(正常)边覆盖染色是对G的边进行染色,使得每一色组都是G的一个边覆盖,使G有(正常)边覆盖染色所需最多颜色数,称为G的边覆盖色数,用X′c(G)表示,已知的结果是对于任意简单图G,都有δ-1≤X′c(G)≤X∧2,(G)≤δ,δ是G的最小度,若X∧2c(G)=δ,则称G是CI类的,否则称为CII类的,本文主要研究了平面图及平衡的安全r分图的分类问题。 相似文献
2.
边覆盖临界图的一些性质 总被引:2,自引:0,他引:2
设G是一个简单图,其顶点集为V(G)而边集为E(G),S∈E(G)称为 G的一个覆盖,如果由S导出的子图为G的一个生成子图. G的边覆盖色数χ'c(G)是E(G,)所能划分成的最大边覆盖数.已知δ-1 ≤χ'c(G)≤δ,由此将χ'c(G)=δ的图称为CI类图,否则称为CII类图.若G是连通CII类图,且G不是完全图,对任意的u,u∈V(G),e=uv( )E(G),都有χ'c(G+e)>χ'c(G)成立,则称G为边覆盖临界的.本文研究了边覆盖临界图的一些性质.即若G为边覆盖临界图,则对任意的u,v∈V(G),若e=uv( )E(G),总存在w∈{u,v},有d(w)≤2δ-2,且w至少与max{d(w)-δ+1,3d(w)-4δ+4}个最小度顶点相邻. 相似文献
3.
4.
图G的一个超f - 边覆盖染色就是它的一个f - 边覆盖染色并且使得图G中的重边染上不同的颜色. 令χHfc(G)是图G存在一个超f - 边覆盖染色时所需最大的颜色数k. χHfc(G)称作是图G的超f - 边覆盖染色色数. 本文讨论重图的超f - 边覆盖染色的存在性并且给出了重图的超f - 边覆盖染色的色数下界. 相似文献
5.
6.
设G(V,E)是阶数至少是3的简单连通图,若f是图G的k-正常边染色,使得对任意的uv∈E(G),C(u)≠C(v),那么称f是图G的k-邻点可区别边染色(k-ASEC),其中C(u)={f(uw)│uw∈E(G)},而χa′s(G)=min{k│存在G的一个k-ASEC},称为G的邻点可区别边色数.本文给出扇的倍图D(Fm)的邻点可区别边色数. 相似文献
7.
图G的正常边染色f满足相邻点的色集合相不互包含时,该染色称为图G的Smarandcchely-邻点可区别边染色,其中S(x)={f(xw)|xw∈E(G)}称之为在f下的顶点x的色集合.该染色称为图G的Smarandchely-邻点可区别边染色.对图G进行的.Smarandchely-邻点可区别边染色所用最少颜色数称为图G的Smarandachely-邻点可区别边色数.讨论了Pm□Pn的Smarandchely-邻点可区别边色数. 相似文献
8.
9.
对简单图G=〈V,E〉及自然数k,令V(Gk) =V(G) ,E(Gk) =E(G)∪{uv|d(u,v) =k},其中d(u,v)表示G中u,v的距离,称图Gk为G的k方图.本文讨论了路的k方图Pkn的均匀点染色、均匀边染色和均匀邻强边染色,利用图的色数的基本性质和构造染色函数的方法,得到相应的色数χev(Pkn) ,χ′ee(Pkn) ,χ′eas(Pkn) .并证明猜想“若图G有m -EASC,则一定有m +1 -EASC”对Pkn是正确的. 相似文献
10.
11.
LetG be a simple graph with vertex setV(G) and edge setE(G). A subsetS ofE(G) is called an edge cover ofG if the subgraph induced byS is a spanning subgraph ofG. The maximum number of edge covers which form a partition ofE(G) is called edge covering chromatic number ofG, denoted by χ′c(G). It known that for any graphG with minimum degreeδ,δ -1 ≤χ′c(G) ≤δ. If χ′c(G) =δ, thenG is called a graph of CI class, otherwiseG is called a graph of CII class. It is easy to prove that the problem of deciding whether a given graph is of CI class or CII class is NP-complete. In this paper, we consider the classification of nearly bipartite graph and give some sufficient conditions for a nearly bipartite graph to be of CI class. 相似文献
12.
假设G是一个1-可扩图.G的1-因子覆盖是G的某些1-因子的集合M使得∪M∈M M=F(G).1-因子数目最小的1.因子覆盖称为excessive factorization.一个excessive factorization中的1.因子数目称为图G的excessive index,记为x:(G).本文我们基于G的耳朵分解和E(C)的依赖关系给出了X'e(G)的上界.对任意正整数k≥3,我们构造出一个图G使得A(G)=3而X'e(G)=k.进而,我们考虑了乘积图的excessive index. 相似文献
13.
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. 相似文献
14.
图G的一个pebbling移动是从一个顶点移走2个pebble, 而把其中的1个pebble移到与其相邻的一个顶点上. 图G 的pebbling数f(G)是最小的正整数n, 使得不论n个pebble 如何放置在G的顶点上, 总可以通过一系列的pebbling移动, 把1个pebble移到图G的任意一个顶点上. 图G 的中间图M(G) 就是在G 的每一条边上插入一个新点, 再把G 上相邻边上的新点用一条边连接起来的图. 对于任意两个连通图G和H, Graham猜测f(G\times H)\leq f(G)f(H). 首先研究了圈的中间图的pebbling 数, 然后讨论了一些圈的中间图满足Graham猜想. 相似文献
15.
本文将一个关于两个不交国的单点粘合的图的LPlaCe谱的受控定理推广到了两个国的多点粘合何形;同时证明了相同的结果对目的Q一回也成立。 相似文献
16.
17.
两个简单图G与H的半强积G·H是具有顶点集V(G)×V(H)的简单图,其中两个顶点(u,v)与(u',v')相邻当且仅当u=u'且vv'∈E(H),或uu'∈E(G)且vv'∈E(H).图的邻点可区别边(全)染色是指相邻点具有不同色集的正常边(全)染色.统称图的邻点可区别边染色与邻点可区别全染色为图的邻点可区别染色.图G的邻点可区别染色所需的最少的颜色数称为邻点可区别染色数,并记为X_a~((r))(G),其中r=1,2,且X_a~((1))(G)与X_a~((2))(G)分别表示G的邻点可区别的边色数与全色数.给出了两个简单图的半强积的邻点可区别染色数的一个上界,并证明了该上界是可达的.然后,讨论了两个树的不同半强积具有相同邻点可区别染色数的充分必要条件.另外,确定了一类图与完全图的半强积的邻点可区别染色数的精确值. 相似文献
18.
An edge (vertex) colored graph is rainbow‐connected if there is a rainbow path between any two vertices, i.e. a path all of whose edges (internal vertices) carry distinct colors. Rainbow edge (vertex) connectivity of a graph G is the smallest number of colors needed for a rainbow edge (vertex) coloring of G. In this article, we propose a very simple approach to studying rainbow connectivity in graphs. Using this idea, we give a unified proof of several known results, as well as some new ones. 相似文献
19.
曲面S的一个极小禁用子图是这样的一个图,它的任何一个顶点的度都不小于3,它不能嵌入在S上,但是删去任何一条边后得到的图能嵌入在S上.本文给出了四种构造一个不可定向曲面的极小禁用子图的方式,即粘合一个顶点,一个图的边被其它的图替换,粘合两个顶点,将一个图放在另一个图的一个曲面嵌入的面内. 相似文献