On a class of polynomially solvable travelling salesman problems
On a class of polynomials associated with the paths in a graph and its application to minimum nodes disjoint path coverings of graphs.
On a conjecture concerning the Petersen graph.
On a discrete Dido-type question.
On a Hamiltonian cycle of the fourth power of a connected graph
In this paper the following theorem is proved: Let be a connected graph of order and let be a matching in . Then there exists a hamiltonian cycle of such that .
On a minimum cycle basis of a graph
On a power of cyclically ordered sets
On a problem of Marco Buratti.
On a problem of P. Vestergaard concerning circuits in graphs
On a problem of R. Häggkvist concerning edge-colourings of graphs
On a problem of walks
In 1995, F. Jaeger and M.-C. Heydemann began to work on a conjecture on binary operations which are related to homomorphisms of De Bruijn digraphs. For this, they have considered the class of digraphs such that for any integer , has exactly walks of length , where is the order of . Recently, C. Delorme has obtained some results on the original conjecture. The aim of this paper is to recall the conjecture and to report where all the authors arrived.
On arbitrarily vertex decomposable unicyclic graphs with dominating cycle
A graph G of order n is called arbitrarily vertex decomposable if for each sequence (n₁,...,nₖ) of positive integers such that , there exists a partition (V₁,...,Vₖ) of vertex set of G such that for every i ∈ 1,...,k the set induces a connected subgraph of G on vertices. We consider arbitrarily vertex decomposable unicyclic graphs with dominating cycle. We also characterize all such graphs with at most four hanging vertices such that exactly two of them have a common neighbour.
On certain extensions of intervals in graphs
On certain regular graphs of girth 5.
On coefficients of circuit polynomials and characteristic polynomials.
On coefficients of path polynomials.
On constant-weight TSP-tours
Is it possible to label the edges of Kₙ with distinct integer weights so that every Hamilton cycle has the same total weight? We give a local condition characterizing the labellings that witness this question's perhaps surprising affirmative answer. More generally, we address the question that arises when "Hamilton cycle" is replaced by "k-factor" for nonnegative integers k. Such edge-labellings are in correspondence with certain vertex-labellings, and the link allows us to determine (up to a constant...
On cubic planar hypohamiltonian and hypotraceable graphs.
On cycles in the coprime graph of integers.
On decompositions of complete graphs into factors with given diameters and radii