A path of a graph is maximal if it is not a proper subpath of any other path of the graph. The path spectrum is the set of lengths of all maximal paths in the graph. A graph is scenic if its path spectrum is a singleton set. In this paper, we give a new proof characterizing all scenic graphs with a Hamiltonian path; this result was first proven by Thomassen in \(1974\). The proof strategy used here is also applied in a companion paper in which we characterize scenic graphs with no Hamiltonian path.

In this paper, we count \(n\)-block BTD\((V, B, R, 3, 2)\) configurations for \(n = 1\) and \(2\). In particular, we list all configuration types and determine formulae for the number of \(n\)-block subsets of a design of each type. A small number of the formulae are shown to be dependent solely on the design parameters. The remainder are shown to be dependent on the number of occurrences of two particular two-block configurations as well as the design parameters. Three new non-isomorphic BTD\((9; 33; 5, 3, 11; 3; 2)\) are given that illustrate the independence of certain configurations.

Sampathkumar and Pushpa Latha (see \({[3]}\)) conjectured that the independent domination number, \(i(T)\), of a tree \(T\) is less than or equal to its weak domination number, \(\gamma_w(T)\). We show that this conjecture is true, prove that \(\gamma_w(T) \leq \beta(T)\) for a tree \(T\), exhibit an infinite class of trees in which the differences \( \gamma_w-i \) and \(\beta – \gamma_w\) can be made arbitrarily large, and show that the decision problem corresponding to the computation of \(\gamma(G)\) is \(NP\)-complete, even for bipartite graphs. Lastly, we provide a linear algorithm to compute \(\gamma_w(T)\) for a tree \(T\).

We give operations on graphs preserving the property of being a \((0,2)\)-graph. In particular, these operations allow the construction of non-vertex-transitive \((0,2)\)-graphs. We also construct a family of regular interval-regular graphs which are not interval monotone, thus disproving a weaker version of a conjecture proposed by H.M. Mulder.

This paper investigates the number of spanning subgraphs of the product of an arbitrary graph \(G\) with the path graphs \(P_n\) on \(n\) vertices that meet certain properties: connectivity, acyclicity, Hamiltonicity, and restrictions on degree. A general method is presented for constructing a recurrence equation \(R(n)\) for the graphs \(G \times P_n\), giving the number of spanning subgraphs that satisfy a given combination of the properties. The primary result is that all constructed recurrence equations are homogeneous linear recurrence equations with integer coefficients. A second result is that the property “having a spanning tree with degree restricted to \(1\) and \(3\)” is a comparatively strong property, just like the property “having a Hamilton cycle”, which has been studied extensively in literature.

Broersma and Hoede studied the \(P_3\)-transformation of graphs and claimed that it is an open problem to characterize all pairs of nonisomorphic connected graphs with isomorphic connected \(P_3\)-graphs. In this paper, we solve the problem to a great extent by proving that the \(P_3\)-transformation is one-to-one on all graphs with minimum degree greater than two. The only cases that remain open are cases where some degree is 1 or 2, and examples indicate that the problem seems to be difficult in these cases. This in some sense can be viewed as a counterpart with respect to \(P_3\)-graphs for Whitney’s result on line graphs.

A graph \(H\) is called a seed graph if there exists a graph \(G\) such that the deletion of any closed neighborhood of \(G\) always results in \(H\). In this paper, we investigate disconnected seed graphs. By degree and order considerations, we show that for certain pairs of connected graphs, \(H_1\) and \(H_2\), \(H_1 \cup H_2\) cannot be a seed graph. Furthermore, for every connected graph \(H\) such that \(K_1 \cup H\) is a seed graph, we show that \(H\) can be obtained by a certain graph product of \(K_2\) and \(H’\), where \(H’\) is itself a seed graph.

The following problem is formulated:

Let \(P(G)\) be a graph parameter and let \(k\) and \(\delta\) be integers such that \(k > \ell \geq 0\). Suppose \(|G| = n\) and for any two \(k\)-subsets \(A, B \subset V(G)\) such that \(|A \cap B| = \ell\) it follows that \(P(\langle A\rangle) = P(\langle B\rangle )\). Characterize \(G\).

We solve this problem for two parameters, the domination number and the number of edges modulo \(m\) (for any \(m \geq \ell\)). These solutions extend and are based on an earlier work that dated back to a 1960 theorem of Kelly and Merriell.

A graph \(G\) is outer-projective-planar if it can be embedded in the projective plane so that every vertex appears on the boundary of a single face. We exhibit obstruction sets for outer-projective-planar graphs with respect to the subdivision, minor, and \(Y\Delta\) orderings. Equivalently, we find the minimal non-outer-projective-planar graphs under these orderings.