May 10, 2024 : CSE Bits
The event is structured to last for 30 minutes, comprising a 20 minute presentation by the speaker followed by a 10 minute Q&A session.It's important to note that this gathering is intended to foster interaction and collaboration among research scholars and students within the department. We encourage all members of the CSE family to attend and contribute to the success of this informal gathering. The details of the speakers are as follows:
1. Dogiparthy Veera Venkata Narayana (CS22S004)
Title: Solitary edges in cubic graphs
Abstract:Extensive research has been conducted on 2-connected cubic (aka 3-regular) graphs. Petersen (1891) proved that every 2-connected cubic graph has a perfect matching; and Schönberger (1934) showed that each edge in a 2-connected cubic graph is part of some perfect matching. In light of these well-known results, we set out to characterize those 2-connected cubic graphs in which every edge is part of at least two perfect matchings.
An edge is referred to as a solitary edge if it belongs to a unique perfect matching. Thus, we can restate our objective as characterizing all 2-connected cubic graphs that do not contain any solitary edges. In the case of 2-connected, there are graphs with n/2 solitary edges, where n is the number of vertices. The problem turns out to be more interesting in the case of 3-connected graphs. We have successfully established a constant upper bound (namely, six) on the number of solitary edges in 3-connected cubic graphs. We provide a complete characterization of all cubic 3-connected graphs that have at least three solitary edges.
Date : Friday, May 10, 2024
Time : 5:00 PM
Venue : Aryabhatta Hall (CSB25)
