Carvalho, Lucchesi and Murty proved that any 1-extendable graph G different from K2 and C2n has at least A(G) edge-disjoint removable ears, and any brick G distinct from K4 and C6 has at least A(G) - 2 removable e...Carvalho, Lucchesi and Murty proved that any 1-extendable graph G different from K2 and C2n has at least A(G) edge-disjoint removable ears, and any brick G distinct from K4 and C6 has at least A(G) - 2 removable edges, where A(G) denotes the maximum degree of G. In this paper, we improve the lower bounds for numbers of removable ears and removable edges of 1-extendable graphs. It is proved that any 1-extendable graph G different from K2 and C2n has at least x′(G) edge-disjoint removable ears, and any brick G distinct from Ka and Ce has at least x′(G) - 2 removable edges, where x′(G) denotes the edge-chromatic number of G. Key words 1-extendable graphs, removable ear, removable edge.展开更多
基金supported by the National Science Foundation of China under Grant No.10831001the Fujian Provincial Department of Education under Grant No.JA08223
文摘Carvalho, Lucchesi and Murty proved that any 1-extendable graph G different from K2 and C2n has at least A(G) edge-disjoint removable ears, and any brick G distinct from K4 and C6 has at least A(G) - 2 removable edges, where A(G) denotes the maximum degree of G. In this paper, we improve the lower bounds for numbers of removable ears and removable edges of 1-extendable graphs. It is proved that any 1-extendable graph G different from K2 and C2n has at least x′(G) edge-disjoint removable ears, and any brick G distinct from Ka and Ce has at least x′(G) - 2 removable edges, where x′(G) denotes the edge-chromatic number of G. Key words 1-extendable graphs, removable ear, removable edge.