You are here

FAU Collections » FAU Research Repository » FAU Theses and Dissertations

Some graph connectivity conditions and their implications

Download pdf | Full Screen View

Date Issued:
2003
Summary:
This dissertation studies two independent problems, each related to a special connectivity condition in a simple graph. The first is a distance-degree condition called cohesion. Given a tree T with n vertices, we analyze the minimum integer f(T) = k, in terms of n, for which any connected k-cohesive graph G contains a copy of T, such that G-V(T) is connected. The problem comes from a generalization of an exercise by Lovasz [L7] in which it is shown that f(K2) = 5. Locke, Tracy and Voss [L5] have proved that in general f(T) > 2n, and in the case in which T is a path, equality is attained. Also Locke [L5.1] proved that f(T) < 4n. Here we improve the upper bound to 4n-6 when T is not a path and to 2n + 2 when T has diameter at most 4. In the particular case of K1,3 we show that f(K1,3) = 2n = 8 is attained. The conjecture that remains open is whether f(T) = 2n for any tree T on n vertices. The second problem studied here is a particular case of the well known relation between the path-connectivity and a set of long cycles, which generate the cycle space of a simple graph. The main conjecture in this topic is by Bondy [B1], and states that if G is a 3-connected graph, with minimum degree at least d and with at least 2d vertices, then every cycle of G can be written as the symmetric difference of an odd number of cycles, each of whose lengths are at least 2d-1. Hartman [H2], Locke [L1, L2, L3], Barovich [BL] and Teng [L6] have proved results related to this conjecture. Here we show that 2-connected, 6-path-connected graphs with at least 9 vertices and minimum degree at least 3 are 6-generated. And more generally, we prove that if a graph G is 2-connected, k-path-connected, and contains a long cycle, then G is (k + 1)-generated, up to some cases which are characterized. The conjecture [L3] of whether, for some constant m, 1/2 < m < 1, every k-path-connected graph is mk-generated, remains open.
Title: Some graph connectivity conditions and their implications.
127 views
38 downloads
Name(s): Abreu, Marien
Florida Atlantic University, Degree Grantor
Locke, Stephen C., Thesis Advisor
Type of Resource: text
Genre: Electronic Thesis Or Dissertation
Issuance: monographic
Date Issued: 2003
Publisher: Florida Atlantic University
Place of Publication: Boca Raton, Fla.
Physical Form: application/pdf
Extent: 75 p.
Language(s): English
Summary: This dissertation studies two independent problems, each related to a special connectivity condition in a simple graph. The first is a distance-degree condition called cohesion. Given a tree T with n vertices, we analyze the minimum integer f(T) = k, in terms of n, for which any connected k-cohesive graph G contains a copy of T, such that G-V(T) is connected. The problem comes from a generalization of an exercise by Lovasz [L7] in which it is shown that f(K2) = 5. Locke, Tracy and Voss [L5] have proved that in general f(T) > 2n, and in the case in which T is a path, equality is attained. Also Locke [L5.1] proved that f(T) < 4n. Here we improve the upper bound to 4n-6 when T is not a path and to 2n + 2 when T has diameter at most 4. In the particular case of K1,3 we show that f(K1,3) = 2n = 8 is attained. The conjecture that remains open is whether f(T) = 2n for any tree T on n vertices. The second problem studied here is a particular case of the well known relation between the path-connectivity and a set of long cycles, which generate the cycle space of a simple graph. The main conjecture in this topic is by Bondy [B1], and states that if G is a 3-connected graph, with minimum degree at least d and with at least 2d vertices, then every cycle of G can be written as the symmetric difference of an odd number of cycles, each of whose lengths are at least 2d-1. Hartman [H2], Locke [L1, L2, L3], Barovich [BL] and Teng [L6] have proved results related to this conjecture. Here we show that 2-connected, 6-path-connected graphs with at least 9 vertices and minimum degree at least 3 are 6-generated. And more generally, we prove that if a graph G is 2-connected, k-path-connected, and contains a long cycle, then G is (k + 1)-generated, up to some cases which are characterized. The conjecture [L3] of whether, for some constant m, 1/2 < m < 1, every k-path-connected graph is mk-generated, remains open.
Identifier: 9780496295531 (isbn), 12030 (digitool), FADT12030 (IID), fau:8945 (fedora)
Note(s): Thesis (Ph.D.)--Florida Atlantic University, 2003.
Subject(s): Trees (Graph theory)
Paths and cycles (Graph theory)
Held by: Florida Atlantic University Libraries
Persistent Link to This Record: http://purl.flvc.org/fcla/dt/12030
Sublocation: Digital Library
Use and Reproduction: Copyright © is held by the author with permission granted to Florida Atlantic University to digitize, archive and distribute this item for non-profit research and educational purposes. Any reuse of this item in excess of fair use or other copyright exemptions requires permission of the copyright holder.
Use and Reproduction: http://rightsstatements.org/vocab/InC/1.0/
Host Institution: FAU
Is Part of Series: Florida Atlantic University Digital Library Collections.