Counterexamples to a conjecture on wiener index of common neighborhood graphs

Abstract

For a simple graph G, the common neighborhood graph con(G) is the graph with the same vertex set as G, with two vertices adjacent in con(G) if they have a common neighbor in G. We describe here constructions of counterexamples to a conjecture of Knor et al. [MATCH Commun. Math. Comput. Chem. 72 (2014), 000-000] that there exists an absolute constant C such that for every graph G it holds that W(con(G)) ≤ C .W(G), where W(G) denotes the Wiener index of G.