Current Search: Locke, Stephen C. (x)
View All Items
 Title
 Cohesion and Nonseparating Trees in connected graphs.
 Creator
 Gottipati, Chenchu B., Locke, Stephen C., Graduate College
 Abstract/Description

If T is a tree on n vertices, n 3, and if G is a connected graph such that dudvd u,v 2n for every pair of distinct vertices of G, it has been conjectured that G must have a nonseparating copy of T. In this note, we prove this result for the special case in which dudv du,v 2n 2 for every pair of distinct vertices of G, and improve this slightly for trees of diameter at least four and for some trees of diameter three. We also characterize the graphs on at most 8 vertices with dudvdu,v 7 for...
Show moreIf T is a tree on n vertices, n 3, and if G is a connected graph such that dudvd u,v 2n for every pair of distinct vertices of G, it has been conjectured that G must have a nonseparating copy of T. In this note, we prove this result for the special case in which dudv du,v 2n 2 for every pair of distinct vertices of G, and improve this slightly for trees of diameter at least four and for some trees of diameter three. We also characterize the graphs on at most 8 vertices with dudvdu,v 7 for every pair of distinct vertices of G, and no nonseparating copy of K_{1,3}
Show less  Date Issued
 2014
 PURL
 http://purl.flvc.org/fau/fd/FA00005818
 Format
 Document (PDF)
 Title
 Reduced path systems and superedgegraceful trees.
 Creator
 Gottipati, Chenchu B., Locke, Stephen C., Graduate College
 Date Issued
 20130412
 PURL
 http://purl.flvc.org/fcla/dt/3361301
 Subject Headings
 Mathematics, Path analysis
 Format
 Document (PDF)
 Title
 Odd sums of long cycles in 2connected graphs.
 Creator
 Teng, Cong., Florida Atlantic University, Locke, Stephen C.
 Abstract/Description

Let G be a 2connected graph with minimum degree d and with at least d + 2 vertices. Suppose that G is not a cycle. Then there is an odd set of cycles, each with length at least d + 1, such that they sum to zero. If G is also nonhamiltonian or bipartite, cycles of length at least 2d can be used.
 Date Issued
 1999
 PURL
 http://purl.flvc.org/fcla/dt/15666
 Subject Headings
 Paths and cycles (Graph theory), Graph theory
 Format
 Document (PDF)
 Title
 Playing Chomp.
 Creator
 Wojtowicz, Bogumila, Florida Atlantic University, Locke, Stephen C.
 Abstract/Description

We investigate the game known as Chomp. This is an example of a combinatorial twoperson nimtype game. Like most of games it has very simple rules, but this does not mean that there is a simple strategy to win. With the help of a computer program we present winning strategies for the first player, since P1 always wins. We also show an isomorphism between Chomp and the Divisor Game.
 Date Issued
 1999
 PURL
 http://purl.flvc.org/fcla/dt/15749
 Subject Headings
 Game theory, Games of chance (Mathematics), Games of strategy (Mathematics)
 Format
 Document (PDF)
 Title
 Long paths and cycles in graphs with large minimum degree.
 Creator
 Barovich, Mark V., Florida Atlantic University, Locke, Stephen C.
 Abstract/Description

Determining which graphs are hamiltonian is a central unsolved problem in graph theory. More generally, the study of long cycles in graphs has been extensive, and there are numerous results on the subject in the mathematical literature. In this dissertation, we survey several of these results. The study of long paths is related to the study of long cycles. In a graph in which every pair of vertices is connected by a long path, every edge lies on a long cycle. We prove that any set of four...
Show moreDetermining which graphs are hamiltonian is a central unsolved problem in graph theory. More generally, the study of long cycles in graphs has been extensive, and there are numerous results on the subject in the mathematical literature. In this dissertation, we survey several of these results. The study of long paths is related to the study of long cycles. In a graph in which every pair of vertices is connected by a long path, every edge lies on a long cycle. We prove that any set of four vertices lying on a common path in a 2connected graph lie on a common long path, generalizing a result of Lovasz. We further exploit the relationship between long paths and long cycles to prove that the cycle spaces of a large class of hamiltonian graphs are generated by long cycles, partially proving a conjecture made by Bondy.
Show less  Date Issued
 1998
 PURL
 http://purl.flvc.org/fcla/dt/12572
 Subject Headings
 Hamiltonian graph theory
 Format
 Document (PDF)
 Title
 Cycle and path double covers of graphs.
 Creator
 Wu, Xuegong, Florida Atlantic University, Locke, Stephen C.
 Abstract/Description

A cycle double cover (CDC) of a graph G is a collection C of cycles of G such that each edge of G belongs to exactly two members of C. P. D. Seymour conjectured that every 2edgeconnected graph admits a CDC. In a similar way, a path double cover (PDC) of graph G is a collection P of paths of G such that each edge of G belongs to exactly two paths of P. If each vertex of G is an end of exactly two paths of P, then P is called a perfect path double cover (PPDC). J. A. Bondy asked if every...
Show moreA cycle double cover (CDC) of a graph G is a collection C of cycles of G such that each edge of G belongs to exactly two members of C. P. D. Seymour conjectured that every 2edgeconnected graph admits a CDC. In a similar way, a path double cover (PDC) of graph G is a collection P of paths of G such that each edge of G belongs to exactly two paths of P. If each vertex of G is an end of exactly two paths of P, then P is called a perfect path double cover (PPDC). J. A. Bondy asked if every simple graph admits a PPDC. In the first part of this thesis, we present some techniques that have been applied to the cycle double cover conjecture and give a detailed study of CDC for some particular graphs. It has been found that this conjecture is true of planar graphs, 3edgecolorable cubic graphs, Cayley graphs and graphs which have a Hamiltonian path. In the second part of this thesis, we mainly deal with path double covers and their variants. We will see that every simple graph admits a PPDC and the PPDC problem is in class P. A detailed summary about the main results discussed in this thesis is included.
Show less  Date Issued
 1991
 PURL
 http://purl.flvc.org/fcla/dt/14687
 Subject Headings
 Paths and cycles (Graph theory)
 Format
 Document (PDF)
 Title
 Some graph connectivity conditions and their implications.
 Creator
 Abreu, Marien, Florida Atlantic University, Locke, Stephen C.
 Abstract/Description

This dissertation studies two independent problems, each related to a special connectivity condition in a simple graph. The first is a distancedegree 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 kcohesive graph G contains a copy of T, such that GV(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]...
Show moreThis dissertation studies two independent problems, each related to a special connectivity condition in a simple graph. The first is a distancedegree 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 kcohesive graph G contains a copy of T, such that GV(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 4n6 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 pathconnectivity 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 3connected 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 2d1. Hartman [H2], Locke [L1, L2, L3], Barovich [BL] and Teng [L6] have proved results related to this conjecture. Here we show that 2connected, 6pathconnected graphs with at least 9 vertices and minimum degree at least 3 are 6generated. And more generally, we prove that if a graph G is 2connected, kpathconnected, 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 kpathconnected graph is mkgenerated, remains open.
Show less  Date Issued
 2003
 PURL
 http://purl.flvc.org/fcla/dt/12030
 Subject Headings
 Trees (Graph theory), Paths and cycles (Graph theory)
 Format
 Document (PDF)
 Title
 Graph labeling and nonseparating trees.
 Creator
 Gottipati, Chenchu B., Locke, Stephen C., Florida Atlantic University, Charles E. Schmidt College of Science, Department of Mathematical Sciences
 Abstract/Description

This dissertation studies two independent problems, one is about graph labeling and the other problem is related to connectivity condition in a simple graph. Graph labeling is a rapidly developing area of research in graph theory, having connections with a variety of applicationoriented areas such as VLSI optimization, data structures and data representation. Furthermore, the connectivity conditions in a simple graphs may help us to study the new aspects of ad hoc networks, social networks...
Show moreThis dissertation studies two independent problems, one is about graph labeling and the other problem is related to connectivity condition in a simple graph. Graph labeling is a rapidly developing area of research in graph theory, having connections with a variety of applicationoriented areas such as VLSI optimization, data structures and data representation. Furthermore, the connectivity conditions in a simple graphs may help us to study the new aspects of ad hoc networks, social networks and web graphs. In chapter 2, we study path systems, reduced path systems and how to construct a super edgegraceful tree with any number of edges using path systems. First, we give an algorithm to reduce a labeled path system to a smaller labeled path system of a different type. First, we investigate the cases (m, k) = (3; 5) and (m, k) = (4; 7), where m is the number of paths and 2k is the length of each path, and then we give a generalization for any k, m = 3 and m = 4. We also describe a procedure to construct a superedgegraceful tree with any number of edges.
Show less  Date Issued
 2014
 PURL
 http://purl.flvc.org/fau/fd/FA00004289, http://purl.flvc.org/fau/fd/FA00004289
 Subject Headings
 Computational complexity, Computer graphics, Graph theory, Integrated circuits  Very large scale integration, Mathematical optimization
 Format
 Document (PDF)