独立数小于4的图的结构研究.pdfVIP

长江大学学报 (自科版)理工卷 2o( 7年12月第t卷第l期 Journal 0f Yangtze University(Nat Sci Edit)SciEng V Dcc．2007，Vo1．4 No．4 · 29 · 独立数小于4的图的结构研究 吴亚平 (江汉大学数学与计算机科学字院，湖北武汉430056；华中师范大学数学与统计学院，湖北武汉430079) 冯丽珠 (江汉大学数学与计算机科学学院，湖北武汉430056) [摘要]图论研究中一个很重要的方面蹙利用图的各种参数来刻画图的结构。通过对图的两个重要不变莹 ． 一 独主教和连通度的分析．分别给出了图G的独立教口(G)一1．2或3．而连通度 (G j壬意取值时图G的 结构特征。 [关键词]连通度；独立数；哈密尔顿圈；团 [中图分类号]()L57．5 [文献标识码]A [文章编号]1673一L409(2007)04一N029一叭 1 基本概念与引理 笔者只研究简单图 。图G一(V( )。E(G))，其中V(( )表示(；的顶点集，E(G)表示G的边集。对 V“∈ (G)，N ，(“)一{ l删∈E(G)， ∈、， ((；)}。若H ( 。则NH(“)一 t {tCT)∈E(G)，t ∈、， (f-f)}o顶点 集 D (G)，若对 V“， ∈D，都有删 (G)，则称D是G的一个独立集。 (G)表示G的连通度，a( )表示( 的最大独立集的阶数。若图G含 生成圈．称G是哈密尔顿图，这个囤称为( 的哈密尔顿囤。若(；：( f )， E(( ))，对V“， ∈ (( )，都有刖∈Eft；)，则称G是完全图。顶点子集尺 (G)，若对V“，u∈R，都有H r∈ (G)，则称尺是( 的一个团。文献[2]给出了当口(G)一，f( )÷1及口(f )一x(G)十2时，图( 中一定有长 至少是 ((；)( _『口(f；)一 (f；))／口(G)圈，这里77一l V(G)l。可知．若。(G)一3． (( )一2，则( 中一定 有K至少是2(“ 一1)／3圈；若口(G)一0。 (G)一l。则G中不一定有K董少是( …2)／ 3圈。笔者将找出满 足L述条件的图G更加具体的结构特征。 引理 l-- 若图G满足 (G)≥a(G)，则G有哈密尔顿圈。 引理2 一 若图( 满足 (G) 口(G)，则G是哈密尔顿连通的。 2 主要结果 命题 l G是完全图的允分必要是图(；满足口((；)一1。 证明 必要性显然。下证充分性 D是G某一一个最大独立集。 【j!lj D!一1。令D— ，则对 V ∈ H(；) -上，． ∈E(G)。故(；是完全图。 命题2 若G≠ 且不是完全图，则a(( )≥2。 证明 由于( ≠ ，则a( )≥l，由命题1知，口(G)≠1。 此 ≥2。 命题3 若图G满足a(G)一矗，则( 至多有矗个连通分支。蔷f 恰好有志个连通分支，则( 每个连通 分支都是完全图。 证明 假设f 有l，，j个连通分支G。，G：，…，G ，且，”走。由命题1和2知，对于 一1，…．，，?，部有口( ) ， ≥ 1。又a(( )一 _EPa((；，)≥Ⅳ 矗，这与题设相矛盾。若G恰好有七个连通分支，则是一a(G)一∑。“。，) ， l ， l ≥走，因此a(G )一1( 一1，…，走)。由命题1知，G每／}、连通分支都是完全图。故命题3结沦成立。 命题4 若图G满足口(G)一2，则：①若 (G)≥2，则( 有哈密尔顿圈；②若 ( )一1，则( 仃2个 1 2 【才】记为尺一，尺。，满足U V(R，)一V(G)，n、， (尺，)一 ，3 q∈尺。，E q，尺：]≠ ，且尺：U q不是完全图， [收稿日期]2007—08—26 [基金项目]武汉市市属高校科技颈目 (20／)6~1 )。 [作者简介]吴丑平(1 979一)，2001年大学毕业，、开师，瘤士生，现主要 事髫也毫壹美教学与研究二 。 · 3O·