Acta mathematica scientia,Series A ›› 2009, Vol. 29 ›› Issue (2): 365-372.

• Articles • Previous Articles     Next Articles

Extending Matchings in Odd Graphs

  

  1. (1. School of Mathematical Sciences, Xiamen University, |Fujian Xiamen 361005|2. Department of Mathematics and Physics, Xiamen University of Technology, Fujian |Xiamen 361024)
  • Received:2007-12-30 Revised:2008-11-30 Online:2009-04-25 Published:2009-04-25
  • Supported by:

    国家自然科学基金(10831001)和福建省教育厅科技项目(JA08223)资助

Abstract:

 Let G be  a graph, and let n, k and d be three nonnegative integers such that n+2k+d≤ |V(G)|-2 and, |V(G)| and n+d have the same parity. If after deleting any n vertices from G the remaining subgraph of G contains an k-matching and each k-matching of the subgraph can be extended to a defect-d-matching of the subgraph, then G is called an (n, k, d)-graph. Liu and Yu[1] first introduced (n, k, d)-graphs, and gave some properties and characterization of (n, k, d)-graphs. A (0, k, 1)-graph may be also called a near k-extendable graph. In the present paper, the authors improve the characterization of (n, k, d)-graphs, and consequently obtain a characterization of near k-extendable graphs. Furthermore, a characterization of near k-extendable bipartite graphs and the relations between near k-extendable graphs and n-factor critical graphs are investigated.

Key words: (n, k, d)-graphs, k-extendable graphs, Near k-extendable graphs, n-factor-critical graphs

CLC Number: 

  • 05C38
Trendmd