Matchings in 3-vertex-critical graphs: The odd case |
| |
Authors: | Nawarat Ananchuen Michael D. Plummer |
| |
Affiliation: | a Department of Mathematics, Silpakorn University, Nakorn Pathom, Thailand b Department of Mathematics, Vanderbilt University, Nashville, TN 37240, USA |
| |
Abstract: | A subset of vertices D of a graph G is a dominating set for G if every vertex of G not in D is adjacent to one in D. The cardinality of any smallest dominating set in G is denoted by γ(G) and called the domination number of G. Graph G is said to be γ-vertex-critical if γ(G-v)<γ(G), for every vertex v in G. A graph G is said to be factor-critical if G-v has a perfect matching for every choice of v∈V(G).In this paper, we present two main results about 3-vertex-critical graphs of odd order. First we show that any such graph with positive minimum degree and at least 11 vertices which has no induced subgraph isomorphic to the bipartite graph K1,5 must contain a near-perfect matching. Secondly, we show that any such graph with minimum degree at least three which has no induced subgraph isomorphic to the bipartite graph K1,4 must be factor-critical. We then show that these results are best possible in several senses and close with a conjecture. |
| |
Keywords: | Matching Factor-critical Domination 3-Vertex-critical |
本文献已被 ScienceDirect 等数据库收录! |
|