The Journal of the Indian Mathematical Society

Y. M. Borse ¹, B. N. Waphare ¹

Affiliations
1 Department of Mathematics, University of Pune, Pune 411007, IN

Abstract

Conlon proved that there exists an even cycle C in a 3-connected graph ≅K₅, of minimum degree at least 4 such that G-E(C) is 2-connected and G - V(C) is connected. We prove that a 2-connected graph G of minimum degree at least 5 has an even cycle C such that G - E(C) is 2-connected and G - V(C) is connected.

Keywords

2-Connected Graph, Even Cycle.

Full Text

     

Y. M. Borse ¹, B. N. Waphare ¹

Affiliations
1 Department of Mathematics, University of Pune, Pune 411 007, IN

Abstract

We call a cycle C of a graph G removable if G - E(C) is connected. In this paper, we obtain sufficient conditions for the existence of a removable cycle in a connected graph G which is edge-disjoint from a connected subgraph of G. Also, a characterization of connected graphs of minimum degree at least 3 having two edge-disjoint removable cycles is obtained in terms of forbidden graphs. We provide sufficient conditions for the existence of removable even cycles, and also for the existence of odd cycles. Further, we handle the problem of determining when a given edge of a connected graph can be guaranteed to lie in some removable cycle.

Keywords

Removable Cycle, Connected Graph.

Full Text