一致图存在的独立数条件  

A Independent Number Condition for the Existence of k-uniform Graphs

作　　者：蔡建生[1] 冯滨鲁[1] 

机构地区：[1]潍坊学院数学与信息科学学院,潍坊261061

出　　处：《应用数学学报》2015年第5期769-774,共6页Acta Mathematicae Applicatae Sinica

基　　金：国家自然科学基金(11571258);山东省自然科学(ZR2013AM001,ZR2013AL016)资助项目

摘　　要：设图G的顶点集为V（G）,k≥4是一个正整数.图G的k-因子是图G的一个支撑子图F使得对于图G的每一个顶点x∈V（G）都有dF（x）=k.一个图G称作是一个k-一致图如果对于图G的每一条边e∈E（G）,都有一个k-因子包含它同时存在另一个k-因子不包含它.本文中我们得到如下结果,设G是一个2-连通的无爪图,k〉4是一个正整数使得k｜V（G）｜是偶数,如果δ（G）≥k＋2并且图的独立数α（G）〈（2k（δ-k-2））/（（k＋1）^2）,则G是一个k-一致图.Let G =（V,E） be a graph with vertex set V（G） and edge set E（G）,k≥4 be an integer.A k-factor of G is a spanning subgraph F of G such that for every x ∈ V（G）satisfying d_F（x） = k.A graph G is called a k-uniform graph if for every e ∈ E（G）,there is a k-factor including it while there is another k-factor excluding it.In this paper we obtain the following result,let G be a 2-connected claw-free graph,k ≥ 4 be an integer such that k｜V（G）｜ is even.If δ（G） ≥ k ＋ 2 and α（G） （2k（δ-k-2））/（k＋1）^2,then G is a k-uniform graph.This result improve the previous related results.

关 键 词：简单图 因子 一致图 独立数 无爪图 

分 类 号：O157.5[理学—数学]