|
| Surface Embedding of Non-Bipartite k-Extendable Graphs |
| Hongliang Lu,David G. L. Wang |
| (School of Mathematics and Statistics, Xi’an Jiaotong University, Xi’an, Shaanxi 710049, China;School of Mathematics and Statistics & MIIT Key Laboratory of Mathematical Theory and Computation in Information Security, Beijing Institute of Technology, Beijing 102400, China) |
| DOI： |
| Abstract: |
| For every surface, we find the minimum number k such that every non-bipartite graph that is embeddable in that surface is not k-extendable. In particular, we construct a family of 3-extendable graphs which we call bow tie graphs. This confirms the existence of an infinite number of 3-extendable non-bipartite graphs that are embeddable in the Klein bottle. |
| Key words: Non-bipartite graph, matching extension, surface embedding. |