English

运筹学学报

• 运筹学 • 上一篇    

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

黄晓娴1  刘岩1,*  吴博思1   

  1. 1. 华南师范大学数学科学学院, 广州 510631
  • 收稿日期:2015-05-28 出版日期:2016-03-15 发布日期:2016-03-15
  • 通讯作者: 刘岩 liuyan@scnu.edu.cn
  • 基金资助:

    国家自然科学基金(No. 11551003), 广州市科技计划项目科学研究专项基金(No. 201510010265)

Some results on fractional k-factor-critical graphs and fractional k-extendable graphs

HUANG Xiaoxian1  LIU Yan1,*  WU Bosi1   

  1. 1.  School of Mathematical Science, South China Normal University, Guangzhou 510631, China
  • Received:2015-05-28 Online:2016-03-15 Published:2016-03-15

PDF

531

摘要：

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

关键词: 分数完美匹配, 分数k-因子临界的, 分数k-可扩的, 分数匹配数

Abstract:

 A simple graph G is said to be fractional k-factor-critical if after deleting any k vertices, the remaining subgraph still has a fractional perfect matching. A graph G is called a fractional k-extendable graph if G has a fractional perfect matching containing M for any k-matching M. In this paper, a sufficient condition for a graph to be fractional k-factor-critical graph and fractional k-extendable graph is given, respectively. Besides, a sufficient and necessary condition for a graph to be fractional k-factor-critical graph is given.

Key words: fractional perfect matching, fractional k-factor-critical, fractional k-extendable, fractional matching number