SC-Hamiltonian graphs and digraphs: New necessary conditions and their impacts

A graph G on n vertices is said to be separable cost constant Hamiltonian (SC-Hamiltonian) if and only if G is Hamiltonian and for any cost matrix C = ( c ( i , j ) ) associated with G where all tours have the same cost, there exist vectors a = ( a 1 , … , a n ) and b = ( b 1 , … , b n ) such that c ( i , j ) = a i + b j ∀ ( i , j ) ∈ E . In this paper we show that for symmetric digraphs strong Hamiltonicity is a necessary condition for SC-Hamiltonicity. As a surprising consequence, we prove that the symmetric digraph obtained from an undirected SC-Hamiltonian graph by edge duplication need not be SC-Hamiltonian. This settles a conjecture of Kabadi and Punnen. We then show that an undirected graph on an even number of nodes having an edge that appears in every Hamiltonian cycle cannot be SC-Hamiltonian. Using this we establish that multiple subdivision of an edge need not preserve SC-Hamiltonicity, disproving a previous claim. Further, we identify other necessary conditions for SC-Hamiltonicity and obtain new classes of SC-Hamiltonian graphs.