Research On Cycle-extendable Graphs

Matching theory is one of the important special topics of graph theory and is in connection with other theoretic problems closely. Motivated by the study of n-extendable graphs,IM-extendable graphs, and PM-compact graphs, we propose two new notions: cycle uniquely extendable graph and induced-cycle extendable graph. We say that a graph G is cycle uniquely extendable if G-V(C) has a unique perfect matching for any even cycle of G. We say that a graph G is cycle-extendable if G-V(C) has a perfect matching for any even cycle C of G. We say that a graph G is induced-cycle extendable if G-V(C) has a perfect matching for any induced even cycle C of G. Here, a cycle C of graph G is called an induced cycle if G[V(C)] is a cycle of G. Obviously, if a graph is cycle extendable, it is induced-cycle extendable. The converse is not true.A graph G is called an H-subdivision of K3,3if G≠K3,3, but G can be obtained from K3,3by replacing some edges in a Hamilton cycle of K3,3by odd paths. Let (?) denote the set of all the graphs G which satisfy the following two conditions:(i) G is a maximal outerplane bipartite graph;(ii) if C is the boundary of the outer face of G, then C has only two22-edges (each of its two ends has degree2in G), which are not adjacent, the remaining edges of C are23-edges (in.G,one end of such edge has degree2and the other end has degree at least3).In this paper, we study cycle uniquely extendable graphs and induced-cycle extend-able graphs. The main results are the following:·A Hamiltonian bipartite graph G is cycle uniquely extendable if and only if G is K3,3or an H-subdivision of K3,3or a spanning Hamiltonian subgraph of the graph in (?);·Partial characterizations of general bipartite graphs which are cycle uniquely ex-tendable;·The conditions of a graph to be induced-cycle extendable.