二部图λ3最优性的一个原子条件.pdfVIP

第 23卷 第 4期 Ih 东 科 学 Vo1．23 No．4 2010年 8月 SHANDONG SCIENCE Aug．2010 文章编号：1002-4026(2010)04-0005-05 二部 图人3最优性的一个原子条件 李鑫，高敬振 ，杨莹莹 (山东师范大学数学科学学院，山东 济南250014) 摘要：设 G= (V，E)是有限简单无向图，是 G的一个边割 ，是一正整数．若 G—U的每个分支的阶至少为 k，则称 U为G的一个 k阶限制边割．定义G的k阶限制边连通度A (G)为G的k阶限制边害Ⅱ中最少的边数， 达到最小的称为 割．定义 (G)=min{(F)：F是G的k阶连通子图 ，其中d(F)表示恰好有一个端点在 F上的边的数 目．如果A (G)= (G)，则称 G是A 最优图．本文给出了二部图A 最优性的一个原子条件． 关键词：阶限制边连通度；几 最优图；原子 中图分类号：0157．5 文献标识码：A AnAtom Condition ofA3-OptimalityofBipartiteGraphs ． LIXin，GAO Jing—zhen，YANGYing—ying (SchoolofMathematics，ShandongNormalUniversity，Jinan250014，China) Abstract：LetG beafinite，simpleandundirected graph，U an edge cutofG andk apositive integer．U isa 一restrictededgecutiftheorderofeverycomponentofG—U isnolessthank．The 一 restrictededgeconnectivityA (G)ofGisthecardinalityofaminimum 一restrictededgecut，aAk cut．Let (F)一FisasubgraphofG— istheedgenumberexactlywithoneendvertexinFand (G)=min{(F)：Fisa 一connetedsubgraphofG}．GisaAk-optimalgraphifA (G)= (G)． Thispaperpresentsanatom condition ofA3一optimalityofbipartitegraphs． Keywords：k-restrictededgeconnectivity；Ak-optimalgraph；atom 1 引言 本文讨论有限简单无向图，后表示一正整数．文中未予定义而直接使用的符号和术语可参考文献 [1]． Esfahanian和Hakimil1-3]引进了图的限制边割，即分割连通图使各分支不含孤立点的边割．更一般地，如果 是图G=(，E)的边割，G—U每个分支的阶至少是 ，则称 为G的 阶限制边割，G称为A 连通 图．定义 A =A (G)=rain{Il： 为 G的k阶限制边割}为 G的k阶限制边连通度 ，达到最小的这种 称为 G的A 割．对A 割 [，]，，都叫A 碎片．最小的A 碎片叫A 原子，其点数记作 (G)．设F是图G的一个子 图，令 (F)表示恰好有一个端点在 F上的边的数 目，定义 = (C)=min{(F)：F是 G的k阶连通子 图1．如果A (G)： (G)，称 G是A 最优 图．图G的最小度6(G)=min{d()：∈ (G)}．对A，BcV，定义 收稿 日期：2010-04一l0 基金项 目：国家 自然科学基金30630073) 作者简介：李鑫(1984．)，女，硕士，研究方向为图论