If \(G\) is a tricyclic Hamiltonian graph of order \(n\) with maximum degree \(3\), then \(G\) has one of two forms, \(X(q,r,s,t)\) and \(Y(q,r,s,t)\), where \(q+r+s+t=n\). We find the graph \(G\) with maximal index by first identifying the graphs of each form having maximal index.

Let \(G = (V_1, V_2; E)\) be a bipartite graph with \(|V_1| = |V_2| = n \geq 2k\), where \(k\) is a positive integer. Let \(\sigma'(G) = \min\{d(u)+d(v): u\in V_1, v\in V_2, uv \not\in E(G)\}\). Suppose \(\sigma'(G) \geq 2k + 2\). In this paper, we will show that if \(n > 2k\), then \(G\) contains \(k\) independent cycles. If \(n = 2k\), then it contains \(k-1\) independent \(4\)-cycles and a \(4\)-path such that the path is independent of all the \(k-1\) \(4\)-cycles.

New results on the enumeration of noncrossing partitions with \(m\) fixed points are presented, using an enumeration polynomial \(P_m(x_1, x_2, \ldots, x_m)\). The double sequence of the coefficients \(a_{m,k}\) of each \(x^k_i\) in \(P_m\) is endowed with some important structural properties, which are used in order to determine the coefficient of each \(x^k_ix^l_j\) in \(P_m\).

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.