Back to search

Georgia Institute of Technology

NON-SEPARATING PATHS IN GRAPHS

Abstract

dc:description.abstract

When developing a theory for 3-connected graphs, Tutte showed that for any 3-connected graph G and any three vertices a, b, c of G, G-c has an a-b path P such that G-P is connected. We call paths non-separating if their removal results in a graph satisfying a certain connectivity constraint. There is a series of work on non-separating paths in graphs and their applications. For any graph G and distinct vertices a,b,c,d in V(G), we give a structural characterization for G not containing a path A from a to b and avoiding c and d such that removing A from G results in a 2-connected graph. Using this structure theorem, we construct a 7-connected such graph. We will also discuss potential applications to other problems, including the 3-linkage conjecture made by Thomassen in 1980. This is based on joint work with Shijie Xie and Xingxing Yu.

Degree

thesis:*
Level thesis:degree_level
Doctoral
Department dc:contributor.department
Mathematics
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2022

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Qian, Yingjie
Advisor dc:contributor.advisor
  • Yu, Xingxing
Committee members dc:contributor.committeemember
  • Bernshteyn, Anton
  • Blekherman, Grigoriy
  • Song, Zi-Xia
  • Wang, Zhiyu

Subjects

dc:subject × 2

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/67276

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Qian, Yingjie. NON-SEPARATING PATHS IN GRAPHS. Doctoral thesis, Georgia Institute of Technology, 2022. http://hdl.handle.net/1853/67276