Back to search

Georgia Institute of Technology

Approximating the circumference of 3-connected claw-free graphs

Abstract

dc:description.abstract

Jackson and Wormald show that every 3-connected K_1,d-free graph, on n vertices, contains a cycle of length at least 1/2 n^g(d) where g(d) = (log_2 6 + 2 log_2 (2d+1))^-1. For d = 3, g(d) ~ 0.122. Improving this bound, we prove that if G is a 3-connected claw-free graph on at least 6 vertices, then there exists a cycle C in G such that |E(C)| is at least c n^g+5, where g = log_3 2 and c > 1/7 is a constant. To do this, we instead prove a stronger theorem that requires the cycle to contain two specified edges. We then use Tutte decomposition to partition the graph and then use the inductive hypothesis of our theorem to find paths or cycles in the different parts of the decomposition.

Degree

thesis:*
Department dc:contributor.department
Mathematics
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2008

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Bilinski, Mark
Advisor dc:contributor.advisor
  • Yu, Xingxing
Committee members dc:contributor.committeemember
  • Duke, Richard
  • Tetali, Prasad
  • Thomas, Robin
  • Vigoda, Eric

Subjects

dc:subject × 5

Identifiers

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

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

Bilinski, Mark. Approximating the circumference of 3-connected claw-free graphs. Georgia Institute of Technology, 2008. http://hdl.handle.net/1853/26516