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.

In this work, we introduce the Interval Permutation Segment (IP-SEG) model that naturally generalizes the geometric intersection models of interval and permutation graphs.
We study properties of two graph classes that arise from the IP-SEG model and present a family of forbidden subgraphs for these classes. In addition, we present polynomial algorithms for the following problems on these classes, when the model is given as part of the input.

Let \( S_n \) be the random walk on \( (0, 1) \). The \( S_n \) have been the subject of intense study; their definition is immediately intuitive. Nevertheless, they are quite intentionally disorderly, and this disorder is mirrored by the fact that, pointwise, \( \left( \frac{S_n}{\sqrt{n}} \mid n \in \mathbb{N}^+ \right) \) behaves quite badly.

In this paper, we provide our results on the fine structure of the random walk that give insight into this behavior.

We utilize the flexible tile model presented in [13] to design self-assembling DNA structures from a graph theory perspective. These tiles represent branched junction molecules whose arms are double strands of DNA.

We consider \( 2 \times n \) triangular lattice graphs \( G_n \), where \( n \) represents the number of triangles. Given a target graph \( G_n \), we determine the minimum number of tile and bond-edge types needed in order to create \( G_n \) as a complete self-assembled complex in three different scenarios. Each scenario corresponds to a distinct level of laboratory constraint.

In the first scenario, graphs of a smaller size than \( G_n \) are allowed. In the second scenario, non-isomorphic graphs of the same size as \( G_n \) are allowed, but not graphs of smaller size. In the third scenario, only graphs isomorphic or larger in size to the target graph are allowed.

We provide optimal tile sets for all \( 2 \times n \) triangular lattice graphs \( G_n \) in Scenario 1 and Scenario 3. We also include some small examples in Scenario 2.