|
|||||
|
|
A lower bound on the number of removable ears of 1-extendable graphs |
|
| Authors: | Shaohui Zhai Xiaofeng Guo |
| Institution: | a Department of Mathematics and Physics, Xiamen University of Technology, Xiamen Fujian 361024, China b Institute of Computing, UNICAMP, Caixa Postal 6176, 13084-971, Campinas, SP, Brazil c School of Mathematical Sciences, Xiamen University, Xiamen Fujian 361005, China |
| Abstract: | Let G be a 1-extendable graph distinct from K2 and C2n. A classical result of Lovász and Plummer (1986) 5, Theorem 5.4.6] states that G has a removable ear. Carvalho et al. (1999) 3] proved that G has at least Δ(G) edge-disjoint removable ears, where Δ(G) denotes the maximum degree of G. In this paper, the authors improve the lower bound and prove that G has at least m(G) edge-disjoint removable ears, where m(G) denotes the minimum number of perfect matchings needed to cover all edges of G. |
| Keywords: | 1-extendable graphs Removable ear Excessive index |
| 本文献已被 ScienceDirect 等数据库收录！ | |