|
|||||
|
|
| 关于分数可消去图的若干结果 | |
| 引用本文： | 禹继国,王娜,卞秋菊,刘桂真.关于分数可消去图的若干结果[J].运筹学学报,2007,11(2):65-72. |
| 作者姓名： | 禹继国 王娜 卞秋菊 刘桂真 |
| 作者单位： | 1. 曲阜师范大学计算机科学学院,山东日照,276826 2. 山东理工大学数学与信息科学学院,山东淄博,255049 3. 山东大学数学与系统科学学院,山东济南,250100 |
| 摘 要： | 令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-边-可消去的与韧度和孤立韧度相关的充分条件。证明了这些结果在一定意义上是最好可能的． |
| 关 键 词： | 运筹学 分数(g f)-可消去的 分数完美匹配 分数k-边-可消去的 |
| 修稿时间： | 2006-05-17 |
Some Results on Fractional Deleted Graphs |
|
| Yu Jiguo,Wang Na,Bian Qiuju,Liu Guizhen.Some Results on Fractional Deleted Graphs[J].OR Transactions,2007,11(2):65-72. | |
| Authors: | Yu Jiguo Wang Na Bian Qiuju Liu Guizhen |
| Institution: | 1. School of Computer Science, Qufu Normal University, Rizhao, Shandong 276826, China; 2.School of Mathematics and Information Science, Shandong University of Technology, Zibo, Shandong, 255049, China; 3.School of Mathematics and System Science, Shandong University, Jinan, Shandong, 250100, China |
| Abstract: | Let G=(V(G), E(G)) be a graph, and let g, f be two integer-valued functions defined on V(G) such that g(x) ≤ f(x) for all x ∈ V(G). G is called fractional (g, f)-deleted if for each edge e of G, there exists a fractional (g, f)-factor Gh such that h(e) = 0, where h is the indicator function of Gh. G is called fractional k-edge-deleted if deleting E' (∩-) E(G), |E'| = k, there exists a fractional perfect matching. In this paper, sufficient conditions related to toughness and isolated toughness for a graph to be fractional 1-deleted, 2-deleted and k-edge-deleted are given. The results are proved to be best possible in some sense. |
| Keywords: | Operations research fractional (g f)-deleted fractional perfect matching fractioual k-edge-deleted |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ | |