Graceful graphs were first studied by Rosa [17]. A graceful labeling \(f\) of a graph G is a one-to-one map from the set of vertices of \(G\) to the set {0.1,., |E(G)|}. where for edges \(xy\), the induced edge labels |f(x) – f (y)| form the set {1,2,., |E(G)|, with no label repeated. In this paper, we investigate the set of labels taken by the central vertex of the star in the graph \(K_{1.m-1} \oplus C_n\), for each graceful labeling. We also study gracefulness of certain unicyclic graphs where paths \(P_3, P_2\) are pendant at vertices of the cycle. For these unicyclic graphs, the deletion of any edge of the cycle does not result in a caterpillar.

An edge-magic total labeling of a graph \(G = (V, E)\) is an assignment of integers \(1,2, …,|V|+|E|\) to the vertices and edges of the graph so that the sum of the labels of any edge \(uv\) and the labels on vertices \(u\) and \(v\) is constant. It is known that the class of complete graphs on \(n\) vertices, \(K_n\), are not edge magic for any n ≥ 7. The edge magic number \(M_E(K_n)\) is defined to be the minimum number t of isolated vertices such that \(K_n \cup tK_1\), is edge magic. In this paper we show that, for n ≥ 10, \(M_E(K_n) ≤ f_{n+1} + 57 – \frac{n^2+n}{2} where \(f_i\) is the \(i^{th}\) Fibonacci number. With the aid of a computer, we also show that \(M_E(K_7) = 4,\, M_E(K_8) = 10\), and \(M_E(K_9) = 19\), answering several questions posed by W. D. Wallis.

A cograph is a simple graph that does not contain an induced path on 4 vertices. A graph G is \(k_{-e} colorable\) if the vertices of G can be colored in k colors such that, for each color, the subgraph induced by the vertices assigned the color is a cograph. A graph that is \(k_{-e} colorable\) and is not \((k-1)_{-e} colorable\), but becomes \((k-1)_{-e} colorable\) whenever a vertex is removed, is called \(k_{-e} critical\) graph. Two general constructions are provided that produce critical graphs from color critical graphs and hypergraphs. A characterization is also given for when a general composition of graphs (path-joins) is critical. The characterization is used to provide an upper bound for the fewest number of vertices of a \(k_{-e} critical\) graph.

We survey Dudeney’s round table problem which asks for a set of Hamilton cycles in the complete graph that uniformly covers the 2-paths of the graph. The problem was proposed about one hundred years ago but it is still unsettled. We mention the history of the problem, known results, gener-alizations, related designs, and some open problems.

Constructions are given for non-cubic, edge-critical Hamilton laceable bigraphs with 3m edges on 2m vertices for all m ≥ 4. The significance of this result is that it shows the conjectured hard upper bound of 3m edges for edge-critical bigraphs on 2m vertices is populated by both cubic and non-cubic cases for all m. This is unlike the situation for the hard 3m-edge lower bound for edge-stable bigraphs where the bound is populated exclusively by cubics.

In this paper, we identify LOW and OLW graphs, find the minimum \(\lambda\) for decomposition of \(\lambda k_n\), into these graphs, and show that for all viable values of \(\lambda\), the necessary conditions are sufficient for LOW- and OLW-decompositions using cyclic decompositions from base graphs.

A maximal independent set is an independent set that is not a proper subset of any other independent set. A twinkle graph W is a connected unicyclic graph with cycle C such that W – x is disconnected for any \(x \in V(C)\). In this paper, we determine the largest number of maximal independent sets and characterize those extremal graphs achieving these values among all twinkle graphs. Using the results on twinkle graphs, we give an alternative proof to determine the largest number of maximal independent sets among all connected graphs with at most one cycle.