Title

Graph minor

Semester

Summer

Date of Graduation

2004

Document Type

Dissertation

Degree Type

PhD

College

Eberly College of Arts and Sciences

Department

Mathematics

Committee Chair

Cun-Quan Zhang.

Abstract

In this paper, we present three results: (1) Let G be a (k + 2)-connected non-(k - 3)-apex graph where k ≥ 2. If G contains three k-cliques, say L 1, L2, L3, such that |Li ∩ Lj| ≤ k - 2 (1 ≤ i < j ≤ 3), then G contains a Kk +2 as a minor. (2) Let G be a 6-connected claw-free graph. If delta(G) ≥ 7 and G contains three disjoint 5-cliques, say Ll, L2, L3, then G contains a K7 as a minor. (3) There is a function h : N → N, such that, for every 4-connected graph G with minimum degree at least five embedded in a surface with Euler genus g and face-width at least h(g), every longest circuit of the graph G has a chord.

Share

COinS