Date & Time: Wednesday, August 26, 2009, 16:00-17:00.
Venue: Ramanujan Hall
Title: Subdivisions of Graphs: A Generalization of Paths and Cycles
Speaker: Chintapalli Sobhan Babu, IIT Bombay
Abstract: The study of subgraphs in a graph is an important topic in graph theory. Paths, trees and cycles are the most basic subgraphs of a graph. Lower bound on the minimum degree which ensures existence of subgraphs that are either paths, trees or cycles have been well studied and many fundamental results exist.
A subdivision of a graph G is a graph obtained from G by replacing some of the edges of G by internally vertex-disjoint paths. Let E(G) be the set of edges and V(G) be the set of vertices in G. We are working on the following question: for what graphs H, and a spanning forest F of H, does every graph of order at least |V(H)| with the sum of degrees of any two non-adjacent vertices at least 2|E(F)|-1 contain a subdivision of H such that only edges in E(H)-E(F) are subdivided.
In this talk we mention some results which are special cases of the above question and prove one particular result.