On the Cordiality of the \(t\)-Uniform Homeomorphs – \(I\)

Abstract

Let \(G\) be a simple graph with vertex set \(V\) and edge set \(E\). A vertex labeling \(\overline{f}: V \to \{0,1\}\) induces an edge labeling \(\overline{f}: E \to \{0,1\}\) defined by \(f(uv) = |f(u) – f(v)|\) .Let \(v_f(0),v_f(1)\) denote the number of vertices \(v\) with \(f(v) = 0\) and \(f(v) = 1\) respectively. Let \(e_f(0),e_f(1)\) be similarly defined. A graph is said to be cordial if there exists a vertex labeling \(f\) such that \(|v_f(0) – vf(1)| \leq 1\) and \(|e_f(0) – e_f(1)| \leq 1\).

A \(t\)-uniform homeomorph \(P_t(G)\) of \(G\) is the graph obtained by replacing all edges of \(G\) by vertex disjoint paths of length \(t\). In this paper we investigate the cordiality of \(P_t(G)\), when \(G\) itself is cordial. We find, wherever possible, a cordial labeling of \(P_t(G)\), whose restriction to \(G\) is the original cordial labeling of \(G\) and prove that for a cordial graph \(G\) and a positive integer \(t\), (1) \(P_t(G)\) is cordial whenever \(t\) is odd, (2) for \(t \equiv 2 \pmod{4}\) a cordial labeling \(g\) of \(G\) can be extended to a cordial labeling \(f\) of \(P_t(G)\) iff \(e_0\) is even, (3) for \(t \equiv 0 \pmod{4}\), a cordial labeling \(g\) of \(G\) can be extended to a cordial labeling \(f\) of \(P_t(G)\) iff \(e_1\) is even.