%0 Journal Article
%T Removable Cycles Avoiding Two Connected Subgraphs
%A Y. M. Borse
%A B. N. Waphare
%J ISRN Discrete Mathematics
%D 2013
%R 10.1155/2013/164535
%X We provide a sufficient condition for the existence of a cycle in a connected graph which is edge-disjoint from two connected subgraphs and of such that is connected. 1. Introduction Prompted by Hobbs' conjecture, Jackson [1] proved that if is a 2-connected simple graph of minimum degree at least and , then contains a cycle such that is 2-connected. Lemos and Oxley [2] generalized this result as follows. Theorem 1. Let be a 2-connected simple graph and let be a subgraph of such that is either 2-connected or . Suppose that for all in and has a cycle that is edge-disjoint from . Then there exists a cycle in that is edge-disjoint from such that is 2-connected. Borse and Waphare [3] obtained the following result for the class of connected graphs which is analogous to the above theorem and is an improvement of a result due to Sinclair [4]. Theorem 2. Let be a connected simple graph and let be a connected subgraph of such that there is a cycle in that is edge-disjoint from . Suppose that for all . Then there exists a cycle in that is edge-disjoint from such that is connected. The problem of the existence of cycles in graphs deletion of whose edges preserve connectedness is well studied in the literature (see [1¨C10]). In this paper, we improve Theorem 2 as follows. Theorem 3. Let be a connected simple graph and let and be connected subgraphs of . Suppose that there are at least two cycles in and further, no two edges of form an edge-cut of . Then there exists a cycle in that is edge-disjoint from both and such that is connected. Let be a connected graph of minimum degree at least three and let and be connected subgraphs of . If has only one cycle, say , then is not connected if a subset of forms an edge-cut of . Therefore, in Theorem 3, we must assume that contains at least two cycles. The following example shows that the condition in Theorem 3 regarding an edge-cut of is necessary. Let and be two disjoint copies of with . Suppose that is an edge of for . Let for . Let be the graph obtained from and by adding two new vertices , and seven new edges , , , , , , and ; see Figure 1. Then is simple, connected and the minimum degree of is 3. Let ,£¿£¿ , and . Then , and are the only cycles of . For , it is easy to see that is not connected as the set is a 2-edge-cut of for each . Figure 1 As a consequence of Theorem 3, we get the following result. Corollary 4. Let be an Eulerian 3-edge-connected simple graph containing at least four mutually edge-disjoint cycles. Then there exist three mutually edge-disjoint cycles , and such that is connected for . We refer to [11]
%U http://www.hindawi.com/journals/isrn.discrete.mathematics/2013/164535/