Menu
A graph \(P_{n}^{2}\), \(n \geq 3\), is the graph obtained from a path \(P_{n}\) by adding edges that join all vertices \(u\) and \(v\) with \(d(u,v) = 2\). A graph \(C_{n}^{+t}\), \(n \geq 3\) and \(1 \leq t \leq n\), is formed by adding a single pendent edge to \(t\) vertices of a cycle of length \(n\). A Web graph \(W(2,n)\) is obtained by joining the pendent vertices of a Helm graph (i.e., a Wheel graph with a pendent edge at each cycle vertex) to form a cycle and then adding a single pendent edge to each vertex of this outer cycle. In this paper, we find the gracefulness of \(P_{n}^{2}\) for any \(n\), of \(C_{n}^{+t}\) for \(n \geq 3\) and \(1 \leq t \leq n\), and of \(W(2,n)\) for \(n \geq 3\). Therefore, three conjectures about labeling graphs —Grace’s, Koh’s, and Gallian’s — are confirmed.