Almost Arbitrary Supersubdivision of Every Graph is Cordial

Abstract

Let $G$ be a graph with $q$ edges. A graph $G^{\ast }$ is called an arbitrary supersubdivision of $G$ if $G^{\ast }$ is obtained from $G$ by replacing every edge $e_i$ of $G$ by a complete bipartite graph $K_{2,m_i}$, such a way that the end vertices of each $e_i$ are identified with the two vertices of the 2-vertices part of $K_{2,m_i}$, after removing the edge $e_i$ from $G$, where $m_i$ of $K_{2,m_i}$ may vary arbitrarily for each edge $e_i$, $1\le i\le q$.

As recognition of cordial graph is an NP-complete, it is interesting and significant to find the graphs whose arbitrary supersubdivision graphs are cordial. In this paper, we show that arbitrary supersubdivision of every bipartite graph is cordial. This result is obtained as a corollary of the general result that “Almost arbitrary supersubdivision of every graph is cordial”, where almost arbitrary supersubdivision is a relaxation of arbitrary supersubdivision graph.

Let $G$ be a graph with edge set $E(G)=E_1\cup E_2$ and $E_1\cap E_2=\mathrm{\varnothing }$. A graph $G$ is called an almost arbitrary supersubdivision graph of $G$ if $G$ is obtained from $G$ by replacing every edge $e_i\in E$ by a complete bipartite graph $K_{2,m_i}$, such a way that the end vertices of each $e_i$ are merged with the two vertices of the 2-vertices part of $K_{2,m_i}$, after removing the edge $e_i$ from $G$, where $m_i$ is chosen as an arbitrary positive integer if $e_i\in E_1$ or else $m_i$ is chosen as an arbitrary even positive integer if $e_i\in E_2$.