New Families of Graceful Disconnected Graphs

M.A. Seoud 1, M.Z. Youssef1
1Math. Dept., Faculty of Science Ain Shams University, Abbassia, Cairo, Egypt.

Abstract

In this paper we extend the definition of pseudograceful graphs given by Frucht [3] to all graphs \(G\) with vertex set \(V(G)\) and edge set \(E(G)\) such that
\(|V(G)| \leq |E(G)| + 1\) and we prove that if \(G\) is a pseudograceful graph, then \(G \cup K_{m,n}\).is pseudograceful
for \(m,n \geq 2\) and \((m,n) \neq (2,2)\) and is graceful for \(m,n \geq 2\). This enables us to obtain several new families of graceful and disconnected graphs.