This paper deals with the problem of constructing Hamiltonian paths of optimal weights in Halin graphs. There are three versions of the Hamiltonian path: none or one or two of end-vertices are specified. We present \(O(|V|)\) algorithms for all the versions of the problem.

It is widely recognized that certain graph-theoretic extremal questions play a major role in the study of communication network vulnerability. These extremal problems are special cases of questions concerning the realizability of graph invariants. We define a CS\((p, q, \lambda, \delta)\) graph as a connected, separable graph having \(p\) points, \(q\) lines, line connectivity \(\lambda\) and minimum degree \(\delta\). In this notation, if the “CS” is omitted the graph is not necessarily connected and separable. An arbitrary quadruple of integers \((a, b, c, d)\) is called CS\((p, q, \lambda, \delta)\) realizable if there is a CS\((p, q, \lambda, \delta)\) graph with \(p = a\), \(q = b\), \(\lambda = c\) and \(\delta = d\). Necessary and sufficient conditions for a quadruple to be CS\((p, q, \lambda, \delta)\) realizable are derived. In recent papers, the author gave necessary and sufficient conditions for \((p, q, \kappa, \Delta)\), \((p, q, \lambda,\Delta )\), \((p, q, \delta, \Delta)\), \((p, q, \lambda, \delta)\) and \((p, q, \kappa, \delta)\) realizability, where \(\Delta\) denotes the maximum degree for all points in a graph and \(\kappa\) denotes the point connectivity of a graph. Boesch and Suffel gave the solutions for \((p, q, \kappa)\), \((p, q, \lambda)\), \((p, q, \delta)\), \((p, \Delta, \delta, \lambda)\) and \((p, \Delta, \delta, \kappa)\) realizability in earlier manuscripts.

An incidence graph of a given graph \(G\), denoted by \(I(G)\), has its own vertex set \(V(I(G)) = \{(ve) | v \in V(G), e \in E(G) \text{ and } v \text{ is incident to } e \text{ in } G\}\) such that the pair \(((ue)(vf))\) of vertices \((ue) (vf) \in V(I(G))\) is an edge of \(I(G)\) if and only if there exists at least one case of \(u = v, e = f, uv = e\) or \(uv = f\). In this paper, we carry out a constructive definition on incidence graphs, and investigate some properties of incidence graphs and some edge-colorings on several classes of them.

The maximum possible toughness among graphs with \(n\) vertices and \(m\) edges is considered for \(m \geq \lceil n^2/4 \rceil\). We thus extend results known for \(m \geq n\lfloor n/3 \rfloor\). When \(n\) is even, all of the values are determined. When \(n\) is odd, some values are determined, and the difficulties are discussed, leaving open questions.

In this paper, we, by means of Rosa’s \(\alpha\)-labelling and \(k\)-graceful labelling, prove that generalized spiders, generalized caterpillars, and generalized path-block chains are graceful under some conditions. Some of the results are stronger than that obtained in \([4]\).

We study convexity with respect to a definition of fractional independence in a graph \(G\) that is quantified over neighbourhoods rather than edges. The graphs that admit a so-called universal maximal fractional independent set are characterized, as are all such sets. A characterization is given of the maximal fractional independent sets which cannot be obtained as a proper convex combination of two other such sets.

In this paper, we consider the relationship between the toughness and the existence of fractional \(f\)-factors. It is proved that a graph $G$ has a fractional \(f\)-factor if \(t(G) \geq \frac{b^2+b}{a}-\frac{b+1}{b}\). Furthermore, we show that the result is best possible in some sense.

It is always fascinating to see what results when seemingly different areas of mathematics overlap. This article reveals one such result; number theory and linear algebra are intertwined to yield complex factorizations of the classic Fibonacci, Pell, Jacobsthal, and Mersenne numbers. Also, in this paper we define a new matrix generalization of the Fibonacci numbers, and using essentially a matrix approach we show some properties of this matrix sequence.

The notion of meandric polygons is introduced in this paper. A bijection exists between the set of meandric polygons and that of closed meanders. We use these polygons to enumerate the set of meanders which have a fixed number of arcs of the meandric curves lying above and below the horizontal line at a given point.