On notions of numerical isomerism of cubic graphs

THOMAS BIER and TU-HOW TAN

Research Report No. 3/2003

Abstract

In this paper we suggest another notion of numerical isomerism extending the K-isomerism defined in [1]. This is named W-isomerism, which is defined in terms of counting the possibilities for extending an s-subset of vertices to an (s+1)-subset,  while keeping the number of edges in both sets under control. It is clear that W-isomerism implies K-isomerism for any pair of graphs. We then show that for cubic graphs K-isomerism implies W-isomerism, while we can exhibit examples of quartic graphs which are K-isomeric yet not W-isomeric.