On prisms, Möbius ladders and the cycle space of dense graphs

Details On prisms, Möbius ladders and the cycle space of dense graphs On prisms, Möbius ladders and the cycle space of dense graphs

2011-12-21

arxiv.org/abs/1112.5101v1

Mathematics

Combinatorics

33 pages; 5 figures

Scientific paper

For a graph X, let f_0(X) denote its number of vertices, d(X) its minimum degree and Z_1(X;Z/2) its cycle space in the standard graph-theoretical sense (i.e. 1-dimensional cycle group in the sense of simplicial homology theory with Z/2-coefficients). Call a graph Hamilton-generated if and only if the set of all Hamilton circuits is a Z/2-generating system for Z_1(X;Z/2). The main purpose of this paper is to prove the following: for every s > 0 there exists n_0 such that for every graph X with f_0(X) >= n_0 vertices, (1) if d(X) >= (1/2 + s) f_0(X) and f_0(X) is odd, then X is Hamilton-generated, (2) if d(X) >= (1/2 + s) f_0(X) and f_0(X) is even, then the set of all Hamilton circuits of X generates a codimension-one subspace of Z_1(X;Z/2), and the set of all circuits of X having length either f_0(X)-1 or f_0(X) generates all of Z_1(X;Z/2), (3) if d(X) >= (1/4 + s) f_0(X) and X is square bipartite, then X is Hamilton-generated. All these degree-conditions are essentially best-possible. The implications in (1) and (2) give an asymptotic affirmative answer to a special case of an open conjecture which according to [European J. Combin. 4 (1983), no. 3, p. 246] originates with A. Bondy.

Affiliated with

Also associated with

No associations

Rating

On prisms, Möbius ladders and the cycle space of dense graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On prisms, Möbius ladders and the cycle space of dense graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On prisms, Möbius ladders and the cycle space of dense graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-193560