共查询到20条相似文献,搜索用时 46 毫秒
1.
关于图中子图的(n,k)—正交因子分解 总被引:1,自引:0,他引:1
设G是一个具有顶点集V(G)和边集E(G)的图.
设g和f是定义在V(G)上的两个整数值函数,使得g(x)f(x)对所有的点x∈V(G)都成立.如果G是一个(mg+n,mf-n)-图,1n<m2k,且g(x)2k-1对所有的点x∈V(G)都成立,则对任意给定具有|E(H)|=nk边的G的子图H,存在G的一个子图G′使G′有一个(g,f)-因子分解(n,k)-正交H. 相似文献
2.
3.
设G=(X,Y,E(G))是一个二分图,分别用V(G)=XUY和E(G)表示G的顶点集和边集.设f是定义在V(G)上的整数值函数且对(A)x∈V(G)有f(x)≥k.设H_1,H_2,…,H_k是G的k个顶点不相交的子图,且|E(H_i)|=m,1≤i≤k.本文证明了每个二分(0,mf-m+1)-图G有一个(0,f)-因子分解正交于Hi(i=1,2,…,k). 相似文献
4.
Eunjeong Yi 《数学学报(英文版)》2015,31(3):367-382
Let G =(V(G), E(G)) be a graph with vertex set V(G) and edge set E(G). For two distinct vertices x and y of a graph G, let RG{x, y} denote the set of vertices z such that the distance from x to z is not equa l to the distance from y to z in G. For a function g defined on V(G) and for U■V(G), let g(U) =∑s∈Ug(s). A real-valued function g : V(G) → [0, 1] is a resolving function of G if g(RG{x, y}) ≥ 1 for any two distinct vertices x, y ∈ V(G). The fractional metric dimension dimf(G)of a graph G is min{g(V(G)) : g is a resolving function of G}. Let G1 and G2 be disjoint copies of a graph G, and let σ : V(G1) → V(G2) be a bijection. Then, a permutation graph Gσ =(V, E) has the vertex set V = V(G1) ∪ V(G2) and the edge set E = E(G1) ∪ E(G2) ∪ {uv | v = σ(u)}. First,we determine dimf(T) for any tree T. We show that 1 dimf(Gσ) ≤1/2(|V(G)| + |S(G)|) for any connected graph G of order at least 3, where S(G) denotes the set of support vertices of G. We also show that, for any ε 0, there exists a permutation graph Gσ such that dimf(Gσ)- 1 ε. We give examples showing that neither is there a function h1 such that dimf(G) h1(dimf(Gσ)) for all pairs(G, σ), nor is there a function h2 such that h2(dimf(G)) dimf(Gσ) for all pairs(G, σ). Furthermore,we investigate dimf(Gσ) when G is a complete k-partite graph or a cycle. 相似文献
5.
Mathematical Notes - Let $$G=(V,E)$$ be a simple graph of order $$n$$ . A set $$S \subseteq V(G)$$ is a perfect dominating set of a graph $$G$$ if every vertex $$v\in V(G)-S$$ is adjacent to... 相似文献
6.
设G=(V,A)是一个有向图,其中V和A分别表示有向图G的点集和弧集.对集合TV(G),如果对于任意点v∈V(G)\T,都存在点u,w∈T(u,w可能是同一点)使得(u,v),(v,w)∈A(G),则称T是G的一个双向控制集.有向图G的双向控制数γ~*(G)是G的最小双向控制集所含点的数目.提出了广义de Bruijn和Kautz有向图的双向控制数的新上界,改进了以前文献中提出的相关结论.此外,对某些特殊的广义de Bruijn和Kautz有向图,通过构造其双向控制集,进一步改进了它们双向控制数的上、下界. 相似文献
7.
On(g,f)—Uniform Graphs 总被引:9,自引:0,他引:9
Thegraphsconsideredinthispaperwillbesimpleundirectedgraphs.LetGbeagraphwithvertexsetV(G)andedgesetE(G).ForavertexxofG,thedegreeofxinGisdenotedbydG(x).Theminimumdegreeandthemaximumdegree0fGaredenotedbyS(G)andb(G),respectively.Letgandfbetw0integer-valuedfunctionsdefined0nV(G)suchthatg(x)5f(x)foreveryx6V(G).Thena(g,f)-factorofGisaspanningsubgraphFofGsatisfyingg(x)SdF(x)5f(x)forallxEV(G).Ifg(x)=f(x)foreachxEV(G),thena(g,f)-factoriscalledanf-factor.Iffisaconstantfunctiontakingthevaluek,… 相似文献
8.
LIU Guizhen & DENG Xiaotie Department of Mathematics Shandong University Jinan China Department of Computer Science The City University of Hong Kong Hong Kong China 《中国科学A辑(英文版)》2005,48(3)
Let G be a bipartite graph with vertex set V(G) and edge set E(G), and let g and f be two nonnegative integer-valued functions defined on V(G) such that g(x)≤ f(x) for every vertex x of V(G). A (g. f)-coloring of G is a generalized edge-coloring in which each color appears at each vertex x at least g(x) and at most f(x) times. In this paper a polynomial algorithm to find a (g. f)-coloring of a bipartite graph with some constraints using the minimum number of colors is given. Furthermore, we show that the results in this paper are best possible. 相似文献
9.
不含三角形的图的λ3-最优性的充分条件 总被引:1,自引:0,他引:1
设G=(V,E)是一个连通图,边集S(?)E是一个3-限制性边割,如果G-S是不连通的并且G-S的每个分支至少有三个点.图G的3-限制性边连通度λ_3(G)是G中最小的一个3-限制性边割的基数.图G是λ_3(G)连通的,如果3-限制性边割存在.G是λ_3-最优的,如果λ_3(G)=ξ_3(G),其中ξ_3(G)=min{|[U,(?)]|:U(?)V,|U|=3 and G[U]是连通的).G[U]表示V的子集U的导出子图,(?)=V\U表示U的补.[U,(?)]是一条边的一个端点在U中另一个端点在(?)中的边的集合.本文给出了不含三角形的图是λ_3-最优的一些充分条件. 相似文献
10.
Acta Mathematicae Applicatae Sinica, English Series - Let G be a graph. We say that G is 2-divisible if for each induced subgraph H of G, either V(H) is a stable set, or V(H) can be partitioned... 相似文献
11.
G=(V,E)表示一个顶点集为V,边集为E的有限简单无向图.若存在映射φ:V(G)→Zk(n)(Zk(n)是由{1,2,…,n}的所有k-元子集构成的集合),满足:(A) uv∈E(G),有φ(u)∩φ(u)=θ,则称φ是G的一个k-重n-顶点染色.本文证明了奇围长至少为5k-7(k=4)或5k-9(k=6)的平面图G... 相似文献
12.
设G是一个图,具有顶点集合V(G)和边集合E(G).设g和f是定义在V(G)上的整数值函数,使对每个x∈V(G),有g(x)≤f(x).图G的一个(g,f)-因子是G的一个支撑子图H,使对每个x∈V(G),有g(x)≤d_H(x)≤f(x).G的一个(g,f)-因子分解是E(G)的边不相交的(g,g)-因子的一个划分.设F={F-1,F_2,…,F_m}为G的一个因子分解,H是G的一个有mr条边的子图.如果每个F_i恰好与H有r条公共边,1≤i≤m,则称Fr-正交于H.本文证明每个(mg+kr,mf-kr)-图含有一个子图R,使R有(g,f)-因子分解r-正交于任意给定的有kr条边的子图,其中m,k和r为正整数且k相似文献
13.
图G=(V,E)的Tutte集定义为X■V(G)满足ω_o(G-X)一|X|=def(G).若不存在Tutte集Y■X,则称X为图G的极大Tutte集.通过找极大extreme集和D-图的极大独立集给出一般图G的找极大Tutte集的两个有效算法,并给出结论:X■V(G)是二部图G的极大Tutte集当且仅当X为二部图G的最小覆盖,从而得到找二部图G的极大Tutte集的一个有效算法. 相似文献
14.
设G是一个二分图具有顶点集V(G)和边集E(G)。设g和f是定义在V(G)上的两个正整值函数使对任意的x∈V(G)有g(x)≤f(x),G的一个(g,f)-因子H是G的一个生成子图满足g(x)≤dH(x)≤f(x)。若图G本身是一个(g,f)-因子,则称G是一个(g,f)-图。本文得到一个(mg,mf)-图具有特殊性质的(g,f)-因子的充分条件,从而推广了文献[6]中的一个结果。 相似文献
15.
不含有图K1,R的图称为K1,r-free图,设G是一个具有顶点集V(G)的图,设n(≥3),a和b是整数,使得b≥a≥1,若b是奇数,设b≥n-1。我们证明了每个连通的K1,r-free图G在b|V(G)|为偶数,它的最小度至少是a n-1,|V(G)≥ (2(a b)-1)(a b-1)/b,以及|NG(x)∪NG(y)|≥a|V(G)|a b对V的任意两个不邻接的点x和y都成立时,G有一个[a,b]因子。 相似文献
16.
17.
图G=(V,E)的每个顶点控制它的闭邻域的每个顶点.S是一个顶点子集合,如果G的每一个顶点至少被S中的两个顶点控制,则称S是G的一个双控制集.把双控制集的最小基数称为双控制数,记为dd(G).本文探讨了双控制数和其它控制参数的一些新关系,推广了[1]的一些结果.并且给出了双控制数的Nordhaus-Gaddum类型的结果. 相似文献
18.
王树勋 《数学的实践与认识》2008,38(18)
设G(V,E)是阶数不小于3的简单连通图,k是自然数,f是从V(G)∪E(G)到1,2,…,k的映射,满足:对任意的uv∈E(G),f(u)≠f(v),f(u)≠f(uv)≠f(v);对任意的uv,uw∈E(G)(v≠w),f(uv)≠f(uw);对任意的uv∈E(G),C(u)≠C(v),其中C(u)={f(u)}∪{f(v)uv∈E(G)}∪{f(uv)uv∈E(G)},则称f是图G的一个邻点强可区别的全染色法,简记作k-AVSDTC,且称χast(G)=min{k G的所有k-AVSDTC}为G的邻点强可区别的全色数.得到了星与轮联图的邻点强可区别的全色数. 相似文献
19.
20.
完全图全符号控制数的较小上界和下确界 总被引:2,自引:0,他引:2
设图G=G(V,E),令函数f∶V∪E→{-1,1},f的权w(f)=∑x∈V∪Ef[x],对V∪E中任一元素,定义f[x]=∑y∈NT[x]f(y),这里NT[x]表示V∪E中x及其关联边、邻点的集合.图G的全符号控制函数为f∶V∪E→{-1,1},满足对所有的x∈V∪E有f[x]1,图G的全符号控制数γT(G)就是图G上全符号控制数的最小权,称其f为图G的γT-函数.本文得到了完全图全符号控制数的一个较小上界和下确界. 相似文献