Decompositions of regular graphs into Knc ∨ 2K2 Original Research Article

The join Knc ∨ 2K2 is the graph obtained by taking a copy of Knc and two disjoint copies of K2, disjoint from Knc, and joining every vertex of Knc to every vertex of 2K2. In this paper we show that for each positive integer n, the graph Knc ∨ 2K2 admits a p-valuation and has gracefulness 4n + 3. Further, for any finite set S0 of positive integers and n ⩾ 2Max {x ∈ ϵ S0} + 1, a new graph valuation, ρ(n; S0), is introduced. Finally, some open problems are proposed.