K-factors in regular graphs

Wai Chee Shiu, Gui Zhen Liu

Research output: Contribution to journalJournal articlepeer-review

16 Citations (Scopus)

Abstract

Plesnik in 1972 proved that an (m - 1)-edge connected m-regular graph of even order has a 1-factor containing any given edge and has another 1-factor excluding any given m - 1 edges. Alder et al. in 1999 showed that if G is a regular (2n + 1)-edge-connected bipartite graph, then G has a 1-factor containing any given edge and excluding any given matching of size n. In this paper we obtain some sufficient conditions related to the edge-connectivity for an n-regular graph to have a k-factor containing a set of edges and (or) excluding a set of edges, where 1 ≤ k ≤ n/2. In particular, we generalize Plesnik's result and the results obtained by Liu et al. in 1998, and improve Katerinis' result obtained 1993. Furthermore, we show that the results in this paper are the best possible.

Original languageEnglish
Pages (from-to)1213-1220
Number of pages8
JournalActa Mathematica Sinica, English Series
Volume24
Issue number7
DOIs
Publication statusPublished - Jul 2008

Scopus Subject Areas

  • General Mathematics
  • Applied Mathematics

User-Defined Keywords

  • Edge-connectivity
  • K-factor
  • Regular graph

Fingerprint

Dive into the research topics of 'K-factors in regular graphs'. Together they form a unique fingerprint.

Cite this