×

On constant-weight TSP-tours. (English) Zbl 1052.05063

The paper looks to labelings of the edges of complete graphs \(K_n\) with distinct integer weights such that each Hamiltonian cycle has exactly the same total weight. The paper shows that such labelings, called { trivial TSP edge-labelings}, exist, and gives a number of equivalent statements for a labeling to be trivial TSP, amongst others: for each 4-cycle with consecutive edges \(e_1, e_2, e_3, e_4\), we have \(w(e_1)+w(e_3) = w(e_2) + w(e_4)\); for each 4-clique in the graph, the total weight for each perfect matching in the clique is identical; for every \(k\), \(0\leq k\leq n-1\), the labeling has constant weight on \(k\)-factors. Related results are also derived.

MSC:

05C78 Graph labelling (graceful graphs, bandwidth, etc.)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
11B75 Other combinatorial number theory
90C35 Programming involving graphs or networks
05C38 Paths and cycles
PDFBibTeX XMLCite
Full Text: DOI Link