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].
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.
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 3Cn20 into odd complete graphs.
dvi
Let G be a K4-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
K4-free graphs.Journal of Graph Theory 26, (1997), pages 61-71.
[MR# 98h:05099]
We investigate lower bounds on the size of K4-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.
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(n2)-time algorithm that finds an
independent set of order at least
(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.
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/15n,
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 nth 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 (n2+5n+3)/(2n2+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 χS(G) of a graph
G=(V,E) is the
smallest order k of a partition
{V1,...,Vk}
of the vertices V(G) such that the subgraph
<Vi>
induced by each subset Vi consists of a
disjoint union of complete subgraphs.
By definition, χS(G) ≤ χ(G),
the chromatic number
if G.
This paper develops properties of this lower bound
for the chromatic number.
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);
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.