Three-dimensional hyperelliptic manifolds

Let X³ = H³, E³, S³, H² × E¹, S² × E¹, T₁(H²), Nil of Solv be one of the eight 3-dimensional geometrics of Thurston [10] and G be a discrete group of isometrics of X³ acting without fixed points. A manifold M³ = X³/G is said to be hyperelliptic if there is an isometric involution on it such that the factor space M³/<> is diffeomorphic to the 3-sphere S³. In analogy with the theory of Riemann surfaces we call involution.In the present paper the existence of hyperelliptic manifolds in each light of the eight 3-dimensional geometrics will be obtained. All the proofs given there will be written in the language of orbifolds whose basic facts can be found in [9].     

Tough graphs and hamiltonian circuits

The toughness of a graph G is defined as the largest real number t such that deletion of any s points from G results in a graph which is either connected or else has at most s/t components. Clearly, every hamiltonian graph is 1-tough. Conversely, we conjecture that for some t₀, every t₀-tough graph is hamiltonian. Since a square of a k-connected graph is always k-tough, a proof of this conjecture with t₀ = 2 would imply Fleischner's theorem (the square of a block is hamiltonian). We construct an infinite family of ($\text{3}\text{2}$)-tough nonhamiltonian graphs.     

Contractions and hamiltonian line graphs

Using the contraction method, we find a best possible condition involving the minimum degree for a triangle-free graph to have a spanning eulerian subgraph.     

Theta characteristics of hyperelliptic graphs

We study theta characteristics of hyperelliptic metric graphs of genus g with no bridge edges. These graphs have a harmonic morphism of degree two to a metric tree that can be lifted to a morphism of degree two of a hyperelliptic curve X over K to the projective line, with K an algebraically closed field of char\({(K) \not =2}\), complete with respect to a non-Archimedean valuation, with residue field k of char\({(k)\not=2}\). The hyperelliptic curve has \({2^{2g}}\) theta characteristics. We show that for each effective theta characteristic on the graph, \({2^{g-1}}\) even and \({2^{g-1}}\) odd theta characteristics on the curve specialize to it; and \({2^g}\) even theta characteristics on the curve specialize to the unique not effective theta characteristics on the graph.     

Edmonds polytopes and weakly hamiltonian graphs

Jack Edmonds developed a new way of looking at extremal combinatorial problems and applied his technique with a great success to the problems of the maximal-weight degreeconstrained subgraphs. Professor C. St. J.A. Nash-Williams suggested to use Edmonds' approach in the context of hamiltonian graphs. In the present paper, we determine a new set of inequalities (the comb inequalities) which are satisfied by the characteristic functions of hamiltonian circuits but are not explicit in the straightforward integer programming formulation. A direct application of the linear programming duality theorem then leads to a new necessary condition for the existence of hamiltonian circuits; this condition appears to be stronger than the ones previously known. Relating linear programming to hamiltonian circuits, the present paper can also be seen as a continuation of the work of Dantzig, Fulkerson and Johnson on the traveling salesman problem.     

Chromatic properties of hamiltonian graphs

We study the problem of the location of real zeros of chromatic polynomials for some families of graphs. In particular, a problem presented by Thomassen (see [On the number of hamiltonian cycles in bipartite graphs, Combin. Probab. Comput. 5 (1996) 437–442.]) is discussed and a result for hamiltonian graphs is presented. An open problem is stated for 2-connected graphs with a hamiltonian path.     

Extremal maximal uniquely hamiltonian graphs

Let G be a graph of order n with exactly one Hamiltonian cycle and suppose that G is maximal with respect to this property. We determine the minimum number of edges G can have.     

Characterization of special hamiltonian graphs

We get a formula for the number of hamiltonian circuits of a graph through which we characterize the special hamiltonian graphs, that is containing a dominant circuit of minimal length.     

Independent sets,cliques and hamiltonian graphs

LetG be ak-connected (k 2) graph onn vertices. LetS be an independent set ofG. S is called essential if there exist two distinct vertices inS which have a common neighbor inG. LetV _r, be a clique which is a complete subgraph ofG. In this paper it is proven that if every essential independent setS ofk + 1 vertices satisfiesS V _r , thenG is hamiltonian, orG{u} is hamiltonian for someu V _r, orG is one of three classes of exceptional graphs. Our theorem generalizes several well-known theorems.     

On line graphs and the hamiltonian index

An extension of a theorem of Chartrand and Wall is obtained and, with it, a bound on the hamiltonian index h(G) of a connected graph G (other than a path) is determined. As a consequence, it is shown that if G is homogeneously traceable, then h(G)?2.     

1-Tough cocomparability graphs are hamiltonian

We show that every 1-tough cocomparability graph has a Hamilton cycle. This settles a conjecture of Chvàtal for the case of cocomparability graphs. Our approach is based on exploiting the close relationship of the problem to the scattering number and the path cover number.     

On hamiltonian colorings for some graphs

For a connected graph G and any two vertices u and v in G, let D(u,v) denote the length of a longest u-v path in G. A hamiltonian coloring of a connected graph G of order n is an assignment c of colors (positive integers) to the vertices of G such that |c(u)−c(v)|+D(u,v)≥n−1 for every two distinct vertices u and v in G. The value of a hamiltonian coloring c is the maximum color assigned to a vertex of G. The hamiltonian chromatic number of G is taken over all hamiltonian colorings c of G. In this paper we discuss the hamiltonian chromatic number of graphs G with . As examples, we determine the hamiltonian chromatic number for a class of caterpillars, and double stars.