- D. Gray, S.C. Locke.
*Split-S-Nim*. Submitted to Congressus Numerantium, March 2019.

Split-S-Nim is a variant of Nim, where S is a subset of the integers. On a player's turn, the player may remove a non-zero number of coins from a pile or, given s∈S, replace a pile of height n with two smaller piles with a total of n+s coins. We consider sets of only even integers with a minimum element of the form 2^{k}or 2^{k}+2 and find Grundy numbers for the normal play version of the game, along with the game where S=ℤ.

- S.J. Curran, S.C. Locke, R.M. Low.
*C*. Submitted to_{4}-face magic labelings on Klein bottle checkerboards**Electronic Journal of Combinatorics**, June 2020, 34pp.

For a graph G = (V,E) embedded in the Klein bottle, let ℱ (G) denote the set of faces of G. Then, G is called a C_{n}-face-magic Klein bottle graph if there exists a bijection f : V(G) → {1,2,...,|V(G)|} such that for any F ∈ ℱ (G) with F isomorphic to C_{n}, the sum of all the vertex labelings along C_{n}is a constant S. Let x_{v}= f(v) for all v ∈ V(G). We call {x_{v}: v ∈ V(G)} a C_{n}-face-magic toroidal labeling on G. We consider the m×n checkerboard, denoted by Ҡ_{m,n}, embedded in the Klein bottle in the natural way. We show that, for m,n ≥ 2, Ҡ_{m,n}admits a C_{4}-face-magic Klein bottle labeling if and only if n is even. We say that a C_{4}-face-magic Klein bottle labeling {x_{i,j}: (i,j) ∈ V(Ҡ_{m,n})} on Ҡ_{m,n}is equatorially balanced if x_{i,j}+ x_{i,n+1−j}= (1/2)S for all (i,j) ∈ V(Ҡ_{m,n}). We show that, when m is odd, a C_{4}-face-magic Klein bottle labeling on Ҡ_{m,n}must be equatorially balanced. Furthermore, when m is odd, we show that, up to symmetries on the Klein bottle, the number of C_{4}-face-magic Klein bottle labelings on the m×4 Klein bottle checkerboard is 2^{m}(m−1)!τ(m), where τ(m) is the number of positive divisors of m. Also, when m is odd, we show that, up to symmetries on the Klein bottle, the minimum number of C_{4}-face-magic Klein bottle labelings on the m×6 Klein bottle checkerboard is (6 • 2^{m}+ 3^{m}+ 4) (m − 1)!.

- S.J. Curran, S.C. Locke, R.M. Low.
*C*._{4}-face magic toroidal labelings on C_{m}×C_{n}**The Art of Discrete and Applied Mathematics 4**(2021), #P1.04, 33pp. [MR4193373]

For a graph G = (V,E) embedded in the torus, let ℱ (G) denote the set of faces of G. Then, G is called a C_{n}-face-magic toroidal graph if there exists a bijection f : V(G) → {1,2,...,|V(G)|} such that for any F ∈ ℱ (G) with F isomorphic to C_{n}, the sum of all the vertex labelings along C_{n}is a constant S. Let x_{v}= f(v) for all v ∈ V(G). We call {x_{v}: v ∈ V(G)} a C_{n}-face-magic toroidal labeling on G. We show that, for all m,n ≥ 2, C_{m}×C_{n}admits a C_{4}-face-magic toroidal labeling if and only if either m = 2, or n = 2, or both m and n are even. We say that a C_{4}-face-magic toroidal labeling {x_{i,j}: (i,j) ∈ V(C_{m}×C_{n})} on C_{m}×C_{n}is antipodal balanced if x_{i,j}+ x_{i+m,j+n}= (1/2)S for all (i,j) ∈ V(C_{m}×C_{n}). We show that there exists an antipodal balanced C_{4}-face-magic toroidal labeling on C_{m}×C_{n}if and only if the parity of m and n are the same. Furthermore, when both m and n are even, an antipodal balanced C_{4}-face-magic toroidal labeling on C_{m}×C_{n}is both row-sum balanced and column-sum balanced. In addition, when m = n is even, an antipodal balanced C_{4}-face-magic toroidal labeling on C_{m}×C_{n}is diagonal-sum balanced.

- S.J. Curran, S.C. Locke.
*C*. To appear in_{4}-face-magic labelings on even order projective grid graphs**PROMS**(Proceedings in Mathematics and Statistics), (accepted March 2022), 25 pp.

For a graph G=(V,E) embedded in the projective plane, let ℱ (G) denote the set of faces of G. Thne, G is called a C_{n}-face-magic projective graph if there exists a bijection f:V(G)→{1,2,...,|V(G)|} such that for any F∈ℱ (G), with F isomorphic to C_{n}, the sum of all the vertex labelings along C_{n}is a constant S. Let x_{v}=f(v) for all v/isin;V(G). We call {x_{v}:v∈V(G)} a C_{n}-face-magic projective labelling on G. We consider the m×n grid graph, denoted P_{m,n}, embedded in the projective plane in the natural way. It is known that for m,n≥2, P_{m,n}admits a C_{4}-face-magic projective labelling if and only if m and n have the same parity.

When m and n are even, a C_{4}-face-magic projective labelling on P_{m,n}has magic value 2mn+2. We show that there are 144 distinct C_{4}-face-magic projective labellings on the 4×4 projective grid graph P_{4,4}(up to symmetries on the projective plane).

- S.J. Curran, S.C. Locke, R.M. Low.
*A variant of Nim played on Boolean matrices.***Integers 23**(2023), #G4, 25 pp.

We consider a version of matrix Nim played on a Boolean matrix. Each player, in turn, removes a non-zero row or column. The last player to remove a row or column wins. We investigate the Boolean matrices that represent the Ferrers diagram of an integer partition. An integer partition in which each summand is greater then the number of terms in the partition is said to be strong. The Grundy numbers of these Boolean matrices consisting of three or fewer rows are determined. This allows us to classify the P-positions and N -positions of Boolean matrices that represent the Ferrers diagram of any strong integer partition.

- S.J. Curran, D. Gray, S.C. Locke, R.M. Low.
*Pyramid Nim*.**Integers 22**(2022), #G2. 15 pp.

Pyramid Nim is played on a directed acyclic graph. Players remove vertices of a path of undominated vertices. We determine Grundy-values for some small games of Pyramid Nim, and Grundy-values for a special class of directed acyclic graphs called triangular pyramids. The rules of the game are quite simple, and the analysis in general may be difficult. These two properties make Pyramid Nim an appealing game.

- S.C. Locke, B. Handley.
*Amalgamation Nim*.**Integers 21**(2021), #G2, 14pp.

We discuss a version of Nim in which players are allowed to use a move from the traditional form of Nim or to amalgamate two piles. We provide winning strategies for games which start with all heaps of height three or less. We also provide a list of losing positions for the three pile game with one heap of height at most eleven.

- W.H. Chan, Ardak Kapbasov, Arman Kapbasov, S.C. Locke, R.M. Low.
*A codex of N- and P- positions in Harary's 'Caterpillar Game'*.**Integers 21**(2021), #G1, 26pp.

Frank Harary proposed the following game: Given a caterpillar C, two players take turns removing the edges of a path. The player who takes the last edge wins the game. In this paper, we completely characterize the N- and P- positions for all caterpillars with spine length zero, one, two, and three. Furthermore, we establish many N-positions for caterpillars with spine length greater than or equal to four.

- D. Gray, S.C. Locke.
*A variant of Nim*.**Discrete Mathematics 341**(2018), 2485-2489. [MR3828758]

We discuss a version of Nim in which players are allowed to use a move from the tradition form of Nim or to split a pile after adding some predetermined number q of coins to the pile. When q is odd or negative, the play proceeds as in regular Nim. For q even and non-negative, we find three patterns: q=0, q=2 and q≥4.

- W.H. Chan, S.C. Locke, R.M. Low, and O.L. Wong.
*A map of the P-positions in 'Nim With a Pass' played on heap sizes of at most four*.**Discrete Applied Mathematics 244**(2018), 44-55. [MR3802534]

Perhaps the most famous combinatorial game is Nim, which was completely analyzed by C.L. Bouton in 1902. Since then, different variants of Nim have been the subject of many research papers. In Guy and Nowakowski's Unsolved Problems in Combinatorial Games, the following entry is found:*"David Gale would like to see an analysis of Nim played with the option of a single pass by either of the players, which may be made at any time up to the penultimate move. It may not be made at the end of the game. Once a player has passed, the game is as in ordinary Nim. The game ends when all heaps have vanished."*In this paper, we determine all of the P-positions (second-player wins) in this particular variant of Nim played on heap sizes of at most four.

- S.C. Locke and S. Perry.
*Labelled Path Systems*.**Congressus Numerantium 229**(2017), 95-100. [MR3752207]

In this note, we give a construction for labelled path systems of shapes (2k,2m), for 1≤k≤7. We also demonstrate a recursive construction for larger values of k assuming that suitable initial configurations can be found.

- S.C. Locke.
*Sum-free graphs*.**Journal of Combinatorics 8**(2017), 349-370. (*Dedicated to Professor J.A. Bondy.*) [MR3610742]

An*n*-vertex graph is sum-free if the vertices can be labelled with {1,2,...,n} such that no vertex gets a label which is the sum of the labels of two of its neighbours. We prove that non-complete graphs with average degree two or less are sum-free. We also prove that graphs with maximum degree three and at least seven vertices are sum-free.

- C. Gottipati and S.C. Locke. Cohesion and non-separating trees in connected graphs.
**Journal of Combinatorial Mathematics and Combinatorial Computing 99**(2016), 69-79. [MR3585733]

If*T*is a tree on*n*vertices,*n ≥ 3*, and if G is a connected graph such that*d(u) + d(v) + d(u,v) ≥ 2n*for every pair of distinct vertices of*G*, it has been conjectured that G must have a non-separating copy of*T*. In this note, we prove this result for the special case in which*d(u) + d(v) + d(u,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.

- 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.

Expository paper:

MR3440477 Reviewed

Alvarez, Josefina(1-NMS); Locke, Stephen(1-FLAT)

Lect. Mat. 36 (2015), no. 2, 181 194.

40A05 (11B68 65B10)

This is a clearly written (in Spanish), rigorously detailed expository article on the basic properties of the real polylogarithm series at negative integer arguments, namely Σ

Note: It should be obvious that it was the first author who translated the paper into Spanish. Any inquiries about this paper directed at the second author would need to be in English.

Florida Atlantic University

777 Glades Road

Boca Raton, Florida 33431-0991

USA

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

Last modified October 14, 2016, by S.C. Locke.