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

A graph GG on nn vertices is said to be separable cost constant Hamiltonian (SC-Hamiltonian  ) if and only if GG is Hamiltonian and for any cost matrix C=(c(i,j))C=(c(i,j)) associated with GG where all tours have the same cost, there exist vectors a=(a1,…,an)a=(a1,…,an) and b=(b1,…,bn)b=(b1,…,bn) such that c(i,j)=ai+bj∀(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.