This paper concerns a labeling problem of the plane graphs \(P_{a,b}\). We discuss the magic labeling of type \((1,1,1)\) and consecutive labeling of type \((1,1,1)\) of the graphs \(P_{a,b}\).

In this note, we prove that the largest non-contractible to \(K^p\) graph of order \(n\) with \(\lceil \frac{2n+3}{3} \rceil \leq p \leq n\) is the Turán’s graph \(T_{2p-n-1}(n)\). Furthermore, a new upper bound for this problem is determined.

If \(u\) and \(v\) are vertices of a graph, then \(d(u,v)\) denotes the distance from \(u\) to \(v\). Let \(S = \{v_1, v_2, \ldots, v_k\}\) be a set of vertices in a connected graph \(G\). For each \(v \in V(G)\), the \(k\)-vector \(c_S(v)\) is defined by \(c_S(v) = (d(v, v_1), d(v, v_2), \ldots, d(v, v_k))\). A dominating set \(S = \{v_1, v_2, \ldots, v_k\}\) in a connected graph \(G\) is a metric-locating-dominating set, or an MLD-set, if the \(k\)-vectors \(c_S(v)\) for \(v \in V(G)\) are distinct. The metric-location-domination number \(\gamma_M(G)\) of \(G\) is the minimum cardinality of an MLD-set in \(G\). We determine the metric-location-domination number of a tree in terms of its domination number. In particular, we show that \(\gamma(T) = \gamma_M(T)\) if and only if \(T\) contains no vertex that is adjacent to two or more end-vertices. We show that for a tree \(T\) the ratio \(\gamma_L(T)/\gamma_M(T)\) is bounded above by \(2\), where \(\gamma_L(G)\) is the location-domination number defined by Slater (Dominating and reference sets in graphs, J. Math. Phys. Sci. \(22 (1988), 445-455)\). We establish that if \(G\) is a connected graph of order \(n \geq 2\), then \(\gamma_M(G) = n-1\) if and only if \(G = K_{1,n-1}\) or \(G = K_n\). The connected graphs \(G\) of order \(n \geq 4\) for which \(\gamma_M(G) = n-2\) are characterized in terms of seven families of graphs.

We deal with the problem of labeling the vertices, edges, and faces of a plane graph in such a way that the label of a face and the labels of the vertices and edges surrounding that face add up to a weight of that face, and the weights of all \(s\)-sided faces constitute an arithmetic progression of difference \(d\). In this paper, we describe various antimagic labelings for the generalized Petersen graph \(P(n, 2)\). The paper concludes with a conjecture.

The edges of a graph can be either directed or signed (\(2\)-colored) so as to make some of the even-length cycles of the underlying graph into alternating cycles. If a graph has a signing in which every even-length cycle is alternating, then it also has an orientation in which every even-length cycle is alternating, but not conversely. The existence of such an orientation or signing is closely related to the existence of an orientation in which every even-length cycle is a directed cycle.

It was shown by Abrham that the number of pure Skolem sequences of order \(n\), \(n \equiv 0\) or \(1 \pmod{4}\), and the number of extended Skolem sequences of order \(n\), are both bounded below by \(2^{\left\lfloor \frac{n}{3} \right\rfloor}\). These results are extended to give similar lower bounds for the numbers of hooked Skolem sequences, split Skolem sequences, and split-hooked Skolem sequences.

Jin and Liu discovered an elegant formula for the number of rooted spanning forests in the complete bipartite graph \(K_{a_1,a_2}\), with \(b_1\) roots in the first vertex class and \(b_2\) roots in the second vertex class. We give a simple proof of their formula, and a generalization for complete \(m\)-partite graphs, using the multivariate Lagrange inverse.

Using a linear space on \(v\) points with all block sizes \(|B| \equiv 0\) or \(1 \pmod{3}\), Doyen and Wilson construct a Steiner triple system on \(2v+1\) points that embeds a Steiner triple system on \(2|B|+1\) points for each block \(B\). We generalise this result to show that if the linear space on \(v\) points is extendable in a suitable way, there is a Steiner quadruple system on \(2v+2\) points that embeds a Steiner quadruple system on \(2(|B|+1)\) points for each block \(B\).

A graph with a graceful labeling (an \(\alpha\)-labeling) is called a graceful (\(\lambda\)-graceful) graph. In this paper, six methods for constructing bigger graceful graphs from a given graceful graph or a set of given \(\lambda\)-graceful graphs are provided. Two of which generalize Koh and others’ Theorems in [2, 3].

Let \(B_2\) be the bananas surface arising from the torus by contracting two different meridians of the torus to a simple point each. It was proved in [8] that there is not a finite Kuratowski theorem for \(B_2\).

A graph is outer-bananas-surface if it can be embedded in \(B_2\) so that all its vertices lie on the same face. In this paper, we prove that the class of the outer-\(B_2\) graphs is closed under minors. In fact, we give the complete set of \(38\) minor-minimal non-outer-\(B_2\) graphs and we also characterize these graphs by a finite list of forbidden topological minors.

We also extend outer embeddings to other pseudosurfaces. The \(S\) pseudosurfaces treated are spheres joined by points in such a way that each sphere has two singular points. We give an excluded minor characterization of outer-\(S\) graphs and we also give an explicit and finite list of forbidden topological minors for these pseudosurfaces.