|Table of Contents|

The Sufficient Conditions for the Existence of Path-Factor Critical Covered Graphs(PDF)

《南京师大学报（自然科学版）》[ISSN:1001-4616/CN:32-1239/N]

Issue:
2023年04期
Page:
11-16
Research Field:
数学
Publishing date:

Info

Title:
The Sufficient Conditions for the Existence of Path-Factor Critical Covered Graphs
Author(s):
Yuan Yuan
(School of Mathematics and Statistics,Hainan University,Haikou 570228,China)
Keywords:
Binding number;  connectivity;  path factor;  P≥t-factor;  P≥t-factor-critical covered graph
PACS:
05C70; 05C38
DOI:
10.3969/j.issn.1001-4616.2023.04.003
Abstract:
Let G be a graph. A spanning subgraph F of G is called a path factor if each component of F is a path. Denote by P≥t-factor the path factor each component of which admits at least t vertices. We say that G is P≥t-factor covered if G has a P≥t-factor containing e for any e∈E(G). For arbitrary SV(G) with |S|=k,if G-S is P≥t-factor covered,then we say G is P≥t-factor-critical covered. In this paper,we present sufficient conditions for graphs to be P≥t-factor-critical covered and construct counterexamples to show that the bounds are best possible in some sense.

References:

[1]BONDY J A,MURTY U S R. Graph Theory[M]. Graduate Texts in Mathematics,London:Springer-Verlag,2008.
[2]ZHOU S Z,SUN Z R. Some existence theorems on path factors with given properties in graphs[J]. Acta mathematica sinica,English series,2020,36(8):917-928.
[3]AKIYAMA J,AVIS D,ERA H. On a{1,2}-factor of a graph[J]. Tru mathematics,1980,16:97-102.
[4]KANEKO A. A necessary and sufficient condition for the existence of a path factor every component of which is a path of length at least two[J]. Journal of combinatorial theory,series B,2003,88:195-218.
[5]ZHANG H P,ZHOU S. Characterizations for P≥2-factor and P≥3-factor covered graphs[J]. Discrete mathematics,2009,309:2067-2076.
[6]ZHOU S Z. Binding numbers and restricted fractional(g,f)-factors in graphs[J]. Discrete applied mathematics,2021,305:350-356.
[7]ZHOU S Z,BIAN Q X,PAN Q R. Path factors in subgraphs[J]. Discrete applied mathematics,2022,319:183-191.
[8]ZHOU S Z,LIU H X,XU Y. A note on fractional ID-[a,b]-factor-critical covered graphs[J]. Discrete applied mathematics,2022,319:511-516.
[9]ZHOU S Z,WU J C,BIAN Q X. On path-factor critical deleted(or covered)graphs[J]. Aequationes mathematicae,2022,96:795-802.
[10]GAO W,WANG W F. Tight binding number bound for P]-factor-critical covered graphs[J]. Discrete applied mathematics,2022,319:511-516.
[9]ZHOU S Z,WU J C,BIAN Q X. On path-factor critical deleted(or covered)graphs[J]. Aequationes mathematicae,2022,96:795-802.
[10]GAO W,WANG W F. Tight binding number bound for b>≥3-factor uniform graphs[J]. Information processing letters,2021,172,106162.

Memo

Memo:
-
Last Update: 2023-12-15