- C. Gottipati and S.C. Locke.
*Reduced path systems and super-edge-graceful trees*.**Congressus Numerantium 216**(2013), 39-52.

We give an algorithm to reduce a labeled path system to a smaller labeled path system of a different type. First, we show as examples 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. Then we give a generalization for*(4,4j+3)*and*(3,2j+1)*. We also describe a procedure to construct super-edge-graceful trees with any number of edges.

- S.C. Locke and Wandi Wei.
*Infinite families of super edge-graceful trees*.**Congressus Numerantium 195**(2009), 125-145. [MR2584291]

We expand the collection of trees produced in [Lee, Sun, Wei, Wen, Yiu (2008)] and provide a lower bound on the number of super-edge-graceful labelings for a subclass of these trees.

- R.E.L. Aldred, R.P Anstee, and S.C. Locke.
*Perfect matchings after vertex deletions*.**Discrete Mathematics 307**(2007), 3048-3054. [MR#2008k:05159]

This paper considers some classes of graphs which are easily seen to have many perfect matchings. Such graphs can be considered robust with respect to the property of having a perfect matching if under vertex deletions (with some mild restrictions), the resulting subgraph continues to have a perfect matching. It is clear that you can destroy the property of having a perfect matching by deleting an odd number of vertices, by upsetting a bipartition or by deleting enough vertices to create an odd component. One class of graphs we consider is the*m×m*lattice graph (or grid graph) for*m*even. Matchings in such grid graphs correspond to coverings of an*m×m*checkerboard by dominoes. If in addition to the easy conditions above, we require that the deleted vertices be*Θ(m*apart, the resulting graph has a perfect matching. The second class of graphs we consider is a^{1/2})*k*-fold product graph consisting of*k*copies of a given graph*G*with the*i*copy joined to the^{th}*i+1*copy by a perfect matching joining copies of the same vertex. We show that, apart from some easy restrictions, we can delete any vertices from the^{st}*k*copy of G and find a perfect matching in the product graph with k suitably large.^{th}

- M. Abreu and S.C. Locke.
*k-path-connectivity and mk-generation: an Upper Bound on m.***Graph Theory: Trends in Mathematics**. Birkhäuser Verlag Basel/Switzerland (2006), 11-19.

We consider simple connected graphs for which there is a path of length at least k between every pair of distinct vertices. We wish to show that in these graphs the cycle space over**Z**_{2}is generated by the cycles of length at least*mk*, where*m=1*for*3≤k≤6*,*m=6/7*for*k=7*,*m≥1/2*for*k≥8*and*m≤3/4+o(1)*for large*k*.

- M. Abreu, D. Labbate, and S.C. Locke.
*6-path-connectivity and 6-generation.***Discrete Mathematics 301**(2005), 20-27. (Combinatorics 2002 conference).

We consider simple connected graphs from which there is a path of length at least 6 between every pair of distinct vertices. We wish to show that in these graphs the cycle space over**Z**_{2}is gnerated by the cycles of length at least 6. Furthermore, we wish to generalize the result for*k*-path-connected graphs which contain a long cycle. See also [Ars92].

- F. Hadlock, F. Hoffman, and S.C. Locke.
*Manhattan graphs*.**Congressus Numerantium 171**(2004), 25-32.

Algorithms for assigning co-ordinates to the vertices of a tree so that each edge is of length one and parallel to an axis.

- M. Abreu and S.C. Locke.
*Non-separating n-vertex trees in (2n+2)-cohesive graphs of diameter at most 4*.**Congressus Numerantium 154**(2002), 21-30.

This is a continuation of the work on cohesion started in [L-V].

- S.C. Locke and
C. Teng.
*Odd sums of long cycles in 2-connected graphs*.**Congressus Numerantium 159**(2002), 19-30.

Let*G*be a*2*-connected 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 non-hamiltonian or bipartite, cycles of length at least*2d*can be used.

- S.C. Locke and
H.-J. Voss.
*A distance-degree condition and non-separating paths: Solution to Problem 10647*[**MAA Monthly 105**, 1998, proposed by S.C.L.]. Incorporated into solution presented in**MAA Monthly 108**, (2001), 470-472.

Let*G*be a connected graph with at least 2 vertices. We say that*G*is*k-cohesive*if*d(u)+d(v)+d(u,v) ≥ k*for every pair of distinct vertices*u*and*v*. In this note, we show that if*G*is*(2n)*-cohesive, with*n ≥ 3*, then*G*contains a non-separating*n*-vertex path. See also [A-L].

- Y. Kaneko and S.C. Locke.
*The minimum degree approach for Paul Seymour's distance 2 conjecture.***Congressus Numerantium 148**(2001), 201-206. [MR# 200k:05078]

Paul Seymour's distance 2 conjecture is as follows. Let*D*be a simple oriented graph. Then*D*contains a vertex*v*such that*d*, where_{++}(v) ≥ d_{+}(v)*d*is the number of vertices with outdistance 1 or 2 from_{++}(v)*v*and*d*is the number of vertices with outdistance 1 from_{+}(v)*v*. In this paper, we prove that the conjecture is true of the minimum degree*δ ≤ 6*.

- M. Barovich and S.C. Locke,
*The cycle space of a 3-connected hamiltonian graph*.**Discrete Mathematics 220**(2000), 13-33. [MR# 2001d:05099]

Let*G*be a*4*-connected graph with minimum degree*d*. Suppose that*G-x*is not hamiltonian, for some vertex*x*of*G*. Then, the cycles of length at least*2d-1*generate the cycle space of*G*.

- S.C. Locke and
D. Witte.
*On non-hamiltonian circulant digraphs of outdegree three*.**Journal of Graph Theory 30**(1999), pages 319-331. [MR# 99m:05069]

Dave Witte, dwitte@math.okstate.edu, has stored preprints: L_{A}T_{E}X 2e file (requires Journal of Graph Theory macros); or PostScript file.

We construct infinitely many connected, circulant digraphs of outdegree three that have no hamiltonian circuit. All of our examples have an even number of vertices, and our examples are of two types: either every vertex in the digraph is adjacent to two diametrically opposite vertices, or every vertex is adjacent to the vertex diametrically opposite to itself.

- S.C. Locke.
Further notes on: largest triangle-free
subgraphs in powers of cycles.
**Ars Combinatoria 49**(1998), 65-77. [MR# 99c:05106]

We derive upper bounds for the number of edges in a triangle-free subgraph of a power of a cycle, extending results of an earlier paper by Bondy and Locke. In this paper, we handle the powers from 17 to 24. In particular, the solution for the case*m=20*is a decomposition of*3C*into odd complete graphs. dvi_{n}^{20}

- S.C. Locke and Feng Lou.
Finding independent sets in K
_{4}-free 4-regular connected graphs.**Journal of Combinatorial Theory, Series B 71**, (1997), 85-110. [MR# 98h:05104]

Let*G*be a K_{4}-free 4-regular connected graph with*n*vertices. Then,*G*contains an independent set of vertices of cardinality at least*7(n-4)/26*. Furthermore, the proof will yield a polynomial-time algorithm which will return an indepednent set of cardinality at least*7(n-4)/26*for any such graph. We also provide a slight improvement over the best previously known result for triangle-free 5-regular graphs.

- K. Fraughnaugh and S.C. Locke.
*Lower bounds on size and independence in**K*-free graphs._{4}**Journal of Graph Theory 26**, (1997), pages 61-71. [MR# 98h:05099]

We investigate lower bounds on the size of*K*-free graphs. For several ranges of independence realtive to order and for graphs with maximum degree 3 and 4, we find sharp lower bounds. We also evaluate Ramsey-type numbers over the classes of graphs with maximum degree 3 and with maximum degree 4._{4}

- K. Fraughnaugh and S.C. Locke.
*Finding independent sets in triangle-free graphs.***S.I.A.M. Journal of Discrete Mathematics 9**(1996), 674-681. [MR# 96f:05180]

Finding a maximum independent set in a graph is well known to be an*NP*-complete problem. Here an*O(n*-time algorithm that finds an independent set of order at least^{2})*(6n-m)/13*in a triangle-free graph with*n*vertices and*m*edges is presented. A tight lower bound on independence in 4-regular triangle-free graphs is*4/13*, so the bound is sharp for this class.

- K. Fraughnaugh
and S.C. Locke.
*11/30 (finding large independent sets in connected triangle-free 3-regular graphs.***Journal of Combinatorial Theory, Series B 65**(1995),51-72. K. Fraughnaugh: KFraughn@carbon.cudenver.edu [MR# 96f:05099]

Staton proved that every 3-regular triangle-free graph has independence ratio at least 5/14 and displayed a graph on 14 vertices which achieved exactly this ratio. We show that the independence ratio for connected 3-regular triangle-free graphs must be at least 11/30-2/15*n*, where*n*is the number of vertices in the graph. This is strictly larger than 5/14 for*n*>14. Furthermore, there is an infinite family of connected 3-regular triangle-free graphs with independence ratio 11/30-1/15n, limiting much further improvement. The proof will yield a polynomial-time algorithm to find an independent set of cardinality at least (11n-4)/30.

- J.A. Bondy
and S.C. Locke.
*Triangle-free subgraphs of powers of cycles.***Graphs and Combinatorics 8**(1992), 109-118. [MR# 93e:05079]

For any graph G, a bipartite subgraph of G must be a triangle-free subgraph of G. However, if G is the*n*th power of a cycle of suitable length, then the maximum number of edges in a triangle-free subgraph H seems to be obtained when H is bipartite. We prove this for*n*between 1 and 16, and present a few related results. See also: later results.

- S.C. Locke.
*Long paths and the cycle space of a graph.***Ars Combinatoria 33**(1992), 77-85. [MR# 94d:05076]

In previous papers, [A-L-W], [EJC85], [ADM85], (and later [B-L]), we established the existence of cycle space bases consisting of long cycles. In each of the cases, we simultaneously proved the existence of long paths between each pair of vertices. In this paper, we conjecture that these two properties are interrelated.

**Example 3**of this paper, the dodecahedron*D*, shows that*f(18)*is at most*17*. Let*H*be the graph obtained by replacing each edge of*D*by a path of length*m*. Then*H*demonstrates that*f(18m)*is at most*17m*. Thus**Conjecture 4**of the paper is false.**Conjecture 5**is true (with constant between*1/2*and*17/18*). In a previous paper, we had shown that if a 2-connected graph*G*has a cycle of length at least*2m-1*, where*m≥2*then*G*is*(m+1)*-generated. Obviously, a*k*-path-connected graph has a cycle of length at least*k+1*and hence must be*((k+2)/2)*-generated. Thus, there is a constant*c*such that every*2*-connected,*k*-path-connected graph must be*(ck)*-generated, and*c*can be chosen to be at least*1/2*. See also [A-L-L].

- S.C. Locke and C.-Q. Zhang.
*Cycles through three vertices in 2-connected graphs.***Graphs and Combinatorics 7**(1991), 265-269. [MR# 93a:05078]

Let G be a 2-connected graph with minumum degree at least d and with at least 2d vertices, and let X be a set of three vertices contained on some cycle of G. Then G has a cycle of length at least 2d through X. This demonstrates that it may be possible to improve the results obtained by Egawa, Glas and Locke.

- F. Hoffman, A.D. Meyerowitz and S.C. Locke.
*A note on cycle double covers of Cayley graphs.***Mathematica Pannonica 2**(1991), 63-66. [MR# 92g:05145]

We prove that any Cayley graph of degree at least 2 must have a cycle double cover.*This might make an interesting exercise for a moderately good graduate student.*

- Y. Egawa, R. Glas and S.C. Locke.
*Cycles and paths through specified vertices in k-connected graphs.***Journal of Combinatorial Theory, Series B, 52**(1991), 20-29. [MR# 92i:05132]

Let G be a k-connected graph with minimum degree d and at least 2d vertices. Then G has a cycle of length at least 2d through any specified set of k vertices. A similar result for paths is also given. This generalizes two results of Dirac.

- B. Alspach,
S.C. Locke and D. Witte.
*The Hamilton spaces of Cayley graphs on abelian groups.***Discrete Mathematics 82**(1990), 113-126. [MR# 91h:05058]

The Hamilton cycles of a graph generate a subspace of the cycle space called the Hamilton space. The Hamilton space of any connected Cayley graph on an abelian group is determined in this paper.

- S.C. Locke.
*A note on bipartite subgraphs of triangle-free regular graphs.***Journal of Graph Theory 14**(1990), 181-185. [MR# 91b:05107]

This note was prompted by the attempted publication of a weaker result by another researcher. We show that a triangle-free k-regular graph G, k ≥ 3, has a bipartite subgraph containing at least (n+2)/(2n+2) of the edges of G if k = 2n, and at least (n^{2}+5n+3)/(2n^{2}+7n+3) of the edges of G if k = 2n+1.

- S.C. Locke and D. Witte.
*Flows in circulant graphs of odd order are sums of Hamilton cycles.***Discrete Mathematics 78**(1989), 105-114. (Volume dedicated to Torrence Parsons.) [MR# 91e:05048]

We show that any flow in any connected circulant graph of odd order can be expressed as a sum of Hamilton cycles.

- M.O. Albertson,
S.T. Hedetniemi, R.E. Jamison and S.C. Locke.
*The subchromatic number of a graph.***Discrete Mathematics 74**(1989), 33-49. [MR# 90f:05057]

The subchromatic number*χ*of a graph_{S}(G)*G=(V,E)*is the smallest order*k*of a partition*{V*of the vertices_{1},...,V_{k}}*V(G)*such that the subgraph*<V*induced by each subset_{i}>*V*consists of a disjoint union of complete subgraphs. By definition,_{i}*χ*, the chromatic number if_{S}(G) ≤ χ(G)*G*. This paper develops properties of this lower bound for the chromatic number.

- S.C. Locke.
*Extremal 3-connected graphs.***Discrete Mathematics 68**(1988), 257-263. [MR# 89:05109]

Let G be a 3-connected graph with minimum degree at least d and at least 2d vertices. For any three vertices x, y, and z, there is a path from x to z through y and having length at least 2d-2. In this paper, we characterize those graphs for which no such path has length exceeding 2d-2.

- J.A. Bondy and S.C. Locke.
*Largest bipartite subgraphs in triangle-free graphs with maximum degree three.***Journal of Graph Theory 10**(1986), 477-504. [MR# 87m:05105]

Let G be a triangle-free graph with maximum degree three. We display a polynomial-time algorithm which returns a bipartite subgraph of G containing at least 4/5 of the edges of G. Furthermore, we characterize the dodecahedron and the Petersen graph as the only connected 3-regular triangle-free graphs for which no bipartite subgraph has more than this proportion.

- S.C. Locke.
*Bipartite density and the independence ratio.***Journal of Graph Theory 10**(1986), 47-53. [MR# 87d:05079]

If a 3-regular graph G has bipartite density b and independence ratio i, then i ≥ (3b-1)/4. A construction demonstrates that this is best possible for all admissible values of b.

- S.C. Locke.
*A basis for the cycle space of a 2-connected graph.***European Journal of Combinatorics 6**(1985), 253-256. [MR# 87g:05138]

We give a new proof of a theorem of Hartman. Let G be a 2-connected graph with minimum degree d. We prove that the cycles of length at least d+1 generate the cycle space of G, unless d is odd and G is the complete graph on d+1 vertices.

- S.C. Locke.
*A generalization of Dirac's theorem.***Combinatorica 5**(1985), 149-159. [MR# 87c:05077]

Let G be an (r+2)-connected graph in which every vertex has degree at least d and which has at least 2d-r vertices. Then, for every path Q of length r and every vertex y not on Q, there is a cycle of length at least 2d-r containing both Q and y.

- S.C. Locke.
*A basis for the cycle space of a 3-connected graph.***Cycles in Graphs, North-Holland Mathematical Studies 115, Annals of Discrete Mathematics 27**(1985), 381-397. [MR# 87h:05136]

Let G be a 3-connected non-hamiltonian graph with minimum degree d. We prove that the cycles of length at least 2d-1 generate the cycle space of G. The requirement that G be non-hamiltonian can be removed if G has at least 4d-5 vertices.

- S.C. Locke.
**Extremal Properties of Paths, Cycles and k-colourable Subgraphs of Graphs.**Ph.D. Thesis, Department of Combinatorics and Optimization, University of Waterloo (1982). (Approximately 260 pages.)

Contains the results of:- Relative lengths of paths and cycles in k-connected graphs (1), (2), (3);
- A generalization of Dirac's Theorem;
- Maximum k-colourable subgraphs;
- Bipartite density and the independence ratio; and
- Largest bipartite subgraphs in triangle-free graphs with maximum degree three.

- extremal examples;
- bipartite subgraphs in regular triangle-free graphs.

- cycle space; (1) (2)
- cycles through specified vertices.

- S.C. Locke.
*Maximum k-colourable subgraphs.***Journal of Graph Theory 6**(1982), 123-132. [MR# 83i:05046]

A lower bound is established on the number of edges in a maximum k-colourable subgraph of a loopless graph G. For the special case of 3-regular graphs, lower bounds are also determined on the maximum number of edges in a bipartite subgraph whose colour classes are of equal size.

- S.C. Locke.
*Relative lengths of paths and cycles in k-connected graphs.***Journal of Combinatorial Theory, Series B, 32**(1982), 206-22. [MR# 83f:05036]

Let G be a k-connected graph, where k ≥ 3. It is shown that if G contains a path L of length m, then G also contains a cycle of length at least (2k-4)m/(3k-4). This result is obtained from a constructive proof that G contains (3k-4)(k-1) cycles which together cover every edge of L at least (2k-4)(k-1) times.

- J.A. Bondy, I. Ben-Arroyo Hartman and S.C. Locke.
*A new proof of a theorem of Dirac.*Proceedings of the Twelfth Southeastern Conference on Combinatorics, Graph Theory and Computing.**Congressus Numerantium 32**(1981), 131-136. [MR# 84c:05055]

We give a new proof of Dirac's theorem by constructing a number of cycles in a 2-connected graph, and deriving a lower bound for their average length. Some related questions are also discussed.

- J.A. Bondy and S.C. Locke.
*Relative lengths of paths and cycles in 3-connected graphs.***Discrete Mathematics 33**(1981), 111-112. [MR#82b:05088]

See the abstract for the general case. This paper contains the proof for the case k = 3, and a basic lemma for the general case.

- J.A. Bondy and S.C. Locke.
*Relative lengths of paths and cycles in k-connected graphs.*Proceedings of the First Joint Canada-France Combinatorial Colloquium,**Annals of Discrete Mathematics 8**(1980). [MR# 81k:05067]

See the abstract for the general case. This paper contains an announcement of the results and a sketch of the proofs.

Florida Atlantic University

777 Glades Road

Boca Raton, Florida 33431-0991

USA

**
Office: Room 286, Science & Engineering
Phone: (561) 297-3350
Fax: (561) 297-2436
URL: http://www.math.fau.edu/locke/abstract.htm
**

Last modified September 30, 2002, by S.C. Locke.