关于分数k-因子临界图与分数k-可扩图的若干结果

一个简单图G, 如果对于V(G)的任意k元子集S, 子图G-S都包含分数完美匹配, 那么称G为分数k-因子临界图. 如果图G的每个k-匹配M都包含在一个分数完美匹配中, 那么称图G为分数k-可扩图. 给出一个图是分数k-因子临界图和分数k-可扩图的充分条件, 并给出一个图是分数k-因子临界图的充分必要条件.     

分数k-因子临界图的条件

设G是-个连通简单无向图,如果删去G的任意k个项点后的图有分数完美匹配,则称G是分数k-因子临界图．给出了G是分数k-因子临界图的韧度充分条件与度和充分条件,这些条件中的界是可达的,并给出G是分数k-因子临界图的一个关于分数匹配数的充分必要条件．     

一个关于图是分数(k,n)-临界的邻域并条件

设G是一个图,以及k是满足1≤k的整数.一个图G在删除任意n个顶点后的子图均含有分数k-因子,则称G是一个分数(k,n)-临界图.给出了图是一个分数(k,n)-临界图的一个邻域并条件,并且该条件是最佳的.     

Discussion on Fractional (a,b, k)-critical Covered Graphs

Acta Mathematicae Applicatae Sinica, English Series - A graph G is called a fractional [a, b]-covered graph if for each e ∈ E(G), G contains a fractional [a, b]-factor covering e. A graph G...     

关于分数(g,f)-因子消去图

一个图称为分数（g,f）－因子消去图，如果去掉图G中的任何一条边e图G仍有一个分数（g,f）－因子。本文分别给出了一个力是分数1－因子消去图和分数2－因子消去图的几个充分条件，并给出一个图有一个分数（g,f）－因子不含给定对集中任何一条边的充要条件。     

图的分数κ-因子

给定图Ｇ＝（Ｖ,Ｅ）．设ａ和ｂ是两个非负整数．是一个函数．如果对所有的均成立,称 ｆ为 Ｇ的一个分数［ａ,ｂ］－ 因子． ａ＝ ｂ＝ κ时,称ｆ为 Ｇ的一个分数 ｋ＝因子．本文给出了一个图有分数 ｋ－因子的充分必要条件．     

图的分数k-因子

给定图G=(V,E).设a和b是两个非负整数.fE→［0,1］是一个函数.如果     

关于分数因子两个开问题的解答

本文指出极小连通二部分数1-因子不一定是极小2-连通图.研究了σ₂（G）与分数k-因子存在性之间的关系,指出存在一个特例在满足阶数n≥4k-5,δ（G）≥k且σ₂（G）≥n条件下,图G不存在分数k-因子.     

分数(g,f)-因子覆盖图

一个图称为分烽（g,f)- 因子覆盖图，如果G中的任何一条边e都包含在一个分数（g,f)- 因子中，并且满足h(e)=1，其中h是分数（g,f)- 因子的导出函数。本文给出了一个图是分数（g,f)- 因子覆盖图的充要条件。     

关于分数可消去图的若干结果

令G=(V(G),E(G))是一个图,并令9和f是两个定义在V(G)上的整数值函数且对所有的x∈V(G)有g(x)≤f(z)成立．若对G的每一条边e都存在G的一个分数(g,f)-因子G_h使得h(e)=0,其中h是G_h的示性函数,则称G是一个分数(g,f)-消去图,若在G中删去E′■E(G),|E′|=k后,所得图有分数完美匹配,则称G是分数k-边-可消去的。本文给出了图是1-可消去,2-可消去和k-边-可消去的与韧度和孤立韧度相关的充分条件。证明了这些结果在一定意义上是最好可能的．     

图有分数因子的度条件

本文研究了图有分数因子的度条件,得到了下面的结果：令k(?)1是一个整数,G是一个连通的n阶图,n(?)4k-3且最小度δ(G)(?)k,若对于每一对不相邻的顶点u,v∈V(G)都有max{d_G(u),d_G(v)}(?)n/2,则G有分数k-因子．并指出该结果在一定意义上是最好可能的。     

图的韧度与分数k-因子的存在性

设G是一个简单无向图,若G不是完全图,G的韧度的一个变形定义为τ(G)=m in{S/(ω(G-S)-1)∶S V(G),ω(G-S)2}.否则,令τ(G)=∞.本文研究了参数τ(G)与分数k-因子的关系,给出了具有某些约束条件的图的分数k-因子存在的一些充分条件,并提出进一步可研究的问题.     

A Result on Fractional (a,b, k)-critical Covered Graphs

Acta Mathematicae Applicatae Sinica, English Series - A fractional [a, b]-factor of a graph G is a function h from E(G) to [0, 1] satisfying $$a \le d_G^h(v) \le b$$ for every vertex v of G, where...     

Fractional Multiples of Graphs and the Density of Vertex-Transitive Graphs

We introduce a construction called the fractional multiple of a graph. This construction is used to settle a question raised by E. Welzl: We show that if G and H are vertex-transitive graphs such that there exists a homomorphism from G to H but no homomorphism from H to G, then there exists a vertex-transitive graph that is homomorphically in between G and H.     

图的孤立韧度与分数因子的存在性

设G是一个简单无向图，若G不是完全图，G的孤立韧度定义为I（G）=min{|S|/I(G-S):S包含于V（G），I(G-S)≥2}。否则，令I（G）=∞。本文引入一个与图的孤立韧度I（G）密切相关的新参数I‘(G)，若G不是完全图时，I‘(G)=min{|S|/(I(G-S)-1):S包含于V（G），I(G-S)≥2}。否则，I‘(G)=∞；本文研究了参数I（G）和I‘(G)的性质以及两者与图的分数k-因子的关系。给出了具有某些约束条件的图的分数因子存在的一些充分条件。并提出进一步的可研究的问题。     

The Extension Degree Conditions for Fractional Factor

In Gao’s previous work, the authors determined several degree conditions of a graph which admits fractional factor in particular settings. It was revealed that these degree conditions are tight if b = f(x) = g(x) = a for all vertices x in G. In this paper, we continue to discuss these degree conditions for admitting fractional factor in the setting that several vertices and edges are removed and there is a difference Δ between g(x) and f(x) for every vertex x in G. These obtained new degree conditions reformulate Gao’s previous conclusions, and show how Δ acts in the results. Furthermore,counterexamples are structured to reveal the sharpness of degree conditions in the setting f(x) =g(x) + Δ.     

The fractional metric dimension of permutation graphs

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.     

On a geometric property of perfect graphs

LetG be a graph,VP(G) its vertex packing polytope and letA(G) be obtained by reflectingVP(G) in all Cartersian coordinates. Denoting byA*(G) the set obtained similarly from the fractional vertex packing polytope, we prove that the segment connecting any two non-antipodal vertices ofA(G) is contained in the surface ofA(G) and thatG is perfect if and only ifA*(G) has a similar property.     

图的分数(g,f)-因子

本文研究了图的分数因子的性质,特别给出了图的弧立韧度这一新概念,研究了孤立韧度与分数因子的关系,文中给出了一个图具有某些约束条件的（g,f）-分数因子的一些充分条件,得到了若干新结果,并提出 了一些可供进一步研究的问题。     

The fractional chromatic number of infinite graphs

The fractional chromatic number of a graph G is the infimum of the total weight that can be assigned to the independent sets of G in such a way that, for each vertex v of G, the sum of the weights of the independent sets containing v is at least 1. In this note we give a graph a graph whose fractional chromatic number is strictly greater than the supremum of the fractional chromatic numbers of its finite subgraphs. This answers a question of Zhu. We also give some grphs for which the fractional chromatic number is not attined, answering another of Zhu. © 1995 John Wiley & Sons, Inc.