A degree condition for fractional [a, b]-covered graphs

被引：19

作者：

Yuan, Yuan ^{[1
]}

Hao, Rong-Xia ^{[1
]}

机构：

[1] Beijing Jiaotong Univ, Dept Math, Beijing 100044, Peoples R China

来源：

INFORMATION PROCESSING LETTERS | 2019年 / 143卷

基金：

中国国家自然科学基金;

关键词：

Network; Combinatorial problems; Degree condition; Fractional; a; b]-covered graph; ORTHOGONAL FACTORIZATIONS; EXISTENCE; EVEN; (A;

D O I：

10.1016/j.ipl.2018.11.002

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

Let G be a graph of order n with delta(G) >= a + 1, and 3 <= a <= b be integers. In this paper, we first show that if G satisfies max{d(G)(X),d(G)(Y)} >= a(n+1)/a+b for each pair of nonadjacent vertices x, y of G, then G is a fractional [a,b]-covered graph. It is a generalization of the known result with a = b = k which is given by Zhou. Furthermore, we show that this result is best possible in some sense. (C) 2018 Elsevier B.V. All rights reserved.

引用

页码：20 / 23

页数：4

共 15 条

[1]

[Anonymous], 2007, Graph Theory

[2] Neighborhood-union condition for an [a, b]-factor avoiding a specified Hamiltonian cycle [J].

Furuya, Michitaka ;

Yashima, Takamasa .

DISCRETE MATHEMATICS, 2017, 340 (06) :1419-1425

[3] Sufficient Condition for the Existence of an Even [a, b]-Factor in Graph [J].

Kouider, Mekkia ;

Ouatiki, Saliha .

GRAPHS AND COMBINATORICS, 2013, 29 (04) :1051-1057

[4]

Li Z., 2002, FRACTIONAL COVERED G, V6, P65

[5] ON (G,F)-COVERED GRAPHS [J].

LIU, GZ .

ACTA MATHEMATICA SCIENTIA, 1988, 8 (02) :181-184

[6] A degree condition for a graph to have (a, b)-parity factors [J].

Liu, Haodong ;

Lu, Hongliang .

DISCRETE MATHEMATICS, 2018, 341 (01) :244-252

[7] Ore-type conditions for the existence of even [2, b]-factors in graphs [J].

Matsuda, H .

DISCRETE MATHEMATICS, 2005, 304 (1-3) :51-61

[8] A generalization of orthogonal factorizations in digraphs [J].

Sun, Zhiren ;

Zhou, Sizhong .

INFORMATION PROCESSING LETTERS, 2018, 132 :49-54

[9]

Zhou S., 2018, ACTA MATH APPL SIN-E, V34, P1

[10] On all fractional (a, b, k)-critical graphs [J].

Zhou, Si Zhong ;

Sun, Zhi Ren .

ACTA MATHEMATICA SINICA-ENGLISH SERIES, 2014, 30 (04) :696-702

← 1 2 →