Forbidden pairs for the matching extendability of graphs with connectivity at least 2 or 3

Zhihao Hui; Junfeng Du; Shipeng Wang; Liming Xiong; Xiaojing Yang

doi:10.1016/j.disc.2019.111694

Forbidden pairs for the matching extendability of graphs with connectivity at least 2 or 3

Zhihao Hui, Junfeng Du, Shipeng Wang^*, Liming Xiong, Xiaojing Yang

^*Corresponding author for this work

School of Mathematics and Statistics

Research output: Contribution to journal › Article › peer-review

Abstract

Let H be a set of connected graphs. A graph G is said to be H-free if G does not contain any member of H as an induced subgraph. A graph G having a perfect matching is called k-extendable if every matching of size k in G can be extended to a perfect matching. In this paper, we characterize the sets H with |H|=2 such that every (k+1)-connected H-free graph G of sufficiently large order permitting a perfect matching is k-extendable for k∈{1,2}.

Original language	English
Article number	111694
Journal	Discrete Mathematics
Volume	343
Issue number	4
DOIs	https://doi.org/10.1016/j.disc.2019.111694
Publication status	Published - Apr 2020

Keywords

Forbidden subgraph
Perfect matching
k-extendable

Access to Document

10.1016/j.disc.2019.111694

Cite this

@article{0f3cc7c92eb6480b8623ca6dffee4de9,

title = "Forbidden pairs for the matching extendability of graphs with connectivity at least 2 or 3",

abstract = "Let H be a set of connected graphs. A graph G is said to be H-free if G does not contain any member of H as an induced subgraph. A graph G having a perfect matching is called k-extendable if every matching of size k in G can be extended to a perfect matching. In this paper, we characterize the sets H with |H|=2 such that every (k+1)-connected H-free graph G of sufficiently large order permitting a perfect matching is k-extendable for k∈{1,2}.",

keywords = "Forbidden subgraph, Perfect matching, k-extendable",

author = "Zhihao Hui and Junfeng Du and Shipeng Wang and Liming Xiong and Xiaojing Yang",

note = "Publisher Copyright: {\textcopyright} 2019 Elsevier B.V.",

year = "2020",

month = apr,

doi = "10.1016/j.disc.2019.111694",

language = "English",

volume = "343",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "4",

}

TY - JOUR

T1 - Forbidden pairs for the matching extendability of graphs with connectivity at least 2 or 3

AU - Hui, Zhihao

AU - Du, Junfeng

AU - Wang, Shipeng

AU - Xiong, Liming

AU - Yang, Xiaojing

PY - 2020/4

Y1 - 2020/4

N2 - Let H be a set of connected graphs. A graph G is said to be H-free if G does not contain any member of H as an induced subgraph. A graph G having a perfect matching is called k-extendable if every matching of size k in G can be extended to a perfect matching. In this paper, we characterize the sets H with |H|=2 such that every (k+1)-connected H-free graph G of sufficiently large order permitting a perfect matching is k-extendable for k∈{1,2}.

AB - Let H be a set of connected graphs. A graph G is said to be H-free if G does not contain any member of H as an induced subgraph. A graph G having a perfect matching is called k-extendable if every matching of size k in G can be extended to a perfect matching. In this paper, we characterize the sets H with |H|=2 such that every (k+1)-connected H-free graph G of sufficiently large order permitting a perfect matching is k-extendable for k∈{1,2}.

KW - Forbidden subgraph

KW - Perfect matching

KW - k-extendable

UR - http://www.scopus.com/inward/record.url?scp=85074486421&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2019.111694

DO - 10.1016/j.disc.2019.111694

M3 - Article

AN - SCOPUS:85074486421

SN - 0012-365X

VL - 343

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 4

M1 - 111694

ER -

Forbidden pairs for the matching extendability of graphs with connectivity at least 2 or 3

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this