Semester

Spring

Date of Graduation

2012

Document Type

Dissertation

Degree Type

PhD

College

Eberly College of Arts and Sciences

Department

Mathematics

Committee Chair

Adam Halasz

Committee Co-Chair

Hong-Jian Lai.

Abstract

A graph G is hamiltonian-connected if any two of its vertices are connected by a Hamilton path (a path including every vertex of G); and G is s-hamiltonian-connected if the deletion of any vertex subset with at most s vertices results in a hamiltonian-connected graph. We prove that the line graph of a (t + 4)-edge-connected graph is (t + 2)-hamiltonian-connected if and only if it is (t + 5)-connected, and for s ≥ 2 every (s + 5)-connected line graph is s-hamiltonian-connected.;For integers l and k with l > 0, and k ≥ 0, Ch( l, k) denotes the collection of h-edge-connected simple graphs G on n vertices such that for every edge-cut X with 2 ≤ |X| ≤ 3, each component of G -- X has at least (n -- k)/l vertices. We prove that for any integer k > 0, there exists an integer N = N( k) such that for any n ≥ N, any graph G ∈ C2(6, k) on n vertices is supereulerian if and only if G cannot be contracted to a member in a well characterized family of graphs.;An orientation of an undirected graph G is a mod (2 p + 1)-orientation if under this orientation, the net out-degree at every vertex is congruence to zero mod 2p + 1. A graph H is mod (2p + 1)-contractible if for any graph G that contains H as a subgraph, the contraction G/H has a mod (2p + 1)-orientation if and only if G has a mod (2p + 1)-orientation (thus every mod (2p + 1)-contractible graph has a mod (2p + 1)-orientation). Jaeger in 1984 conjectured that every (4p)-edge-connected graph has a mod (2p + 1)-orientation. It has also been conjectured that every (4p + 1)-edge-connected graph is mod (2 p + 1)-contractible. We investigate graphs that are mod (2 p + 1)-contractible, and as applications, we prove that a complete graph Km is (2p + 1)-contractible if and only if m ≥ 4p + 1; that every (4p -- 1)-edge-connected K4-minor free graph is mod (2p + 1)-contractible, which is best possible in the sense that there are infinitely many (4p -- 2)-edge-connected K4-minor free graphs that are not mod (2p + 1)-contractible; and that every (4p)-connected chordal graph is mod (2p + 1)-contractible. We also prove that the above conjectures on line graphs would imply the truth of the conjectures in general, and that if G has a mod (2p + 1)-orientation and delta(G) ≥ 4p, then L(G) also has a mod (2p + 1)-orientation.;The design of an n processor network with given number of connections from each processor and with a desirable strength of the network can be modelled as a degree sequence realization problem with certain desirable graphical properties. A nonincreasing sequence d = ( d1, d2, ···, dn) is graphic if there is a simple graph G with degree sequence d. It is proved that for a positive integer k, a graphic nonincreasing sequence d has a simple realization G which has k-edge-disjoint spanning trees if and only if either both n = 1 and d1 = 0, or n ≥ 2 and both dn ≥ k and i=1n di ≥ 2k(n -- 1).;We investigate the emergence of specialized groups in a swarm of robots, using a simplified version of the stick-pulling problem [56], where the basic task requires the collaboration of two robots in asymmetric roles. We expand our analytical model [57] and identify conditions for optimal performance for a swarm with any number of species. We then implement a distributed adaptation algorithm based on autonomous performance evaluation and parameter adjustment of individual agents. While this algorithm reliably reaches optimal performance, it leads to unbounded parameter distributions. Results are improved by the introduction of a direct parameter exchange mechanism between selected high- and low-performing agents. The emerging parameter distributions are bounded and fluctuate between tight unimodal and bimodal profiles. Both the unbounded optimal and the bounded bimodal distributions represent partitions of the swarm into two specialized groups.

Download

Share

COinS