Our purpose is to determine the minimum integer \(f_i(m)\) (\(g_i(m)\), \(h_i(m)\) respectively) for every natural \(m\), such that every digraph \(D\), \(f_i(m)\)-connected, (\(g_i(m)\), \(h_i(m)\)-connected respectively) and \(\alpha^i(D) \leq m\) is hamiltonian (D has a hamilton path, D is hamilton connected respectively), (\(i = 0,1, 2\)). We give exact values of \(f_i(m)\) and \(g_i(m)\) for some particular values of \(m\). We show the existence of \(h_2(m)\) and that \(h_2(1) = 1\), \(h_2(2) = 4\) hold.

A two-valued function \(f\) defined on the vertices of a graph \(G = (V,E)\), \(f: V \to \{-1,1\}\), is a signed dominating function if the sum of its function values over any closed neighborhoods is at least one. That is, for every \(v \in V\), \(f(N[v]) \geq 1\), where \(N[v]\) consists of \(v\) and every vertex adjacent to \(v\). The function \(f\) is a majority dominating function if for at least half the vertices \(v \in V\), \(f(N[v]) \geq 1\). The weight of a signed (majority) dominating function is \(f(V) = \sum f(v)\). The signed (majority) domination number of a graph \(G\), denoted \(\gamma_s(G)\) (\(\gamma_{\text{maj}}(G)\), respectively), equals the minimum weight of a signed (majority, respectively) dominating function of \(G\). In this paper, we establish an upper bound on \(\gamma_s(G)\) and a lower bound on \(\gamma_{\text{maj}}(G)\) for regular graphs \(G\).

A pseudosurface is obtained from a collection of closed surfaces by identifying some points. It is shown that a pseudosurface \(S\) is minor-closed if and only if \(S\) consists of a pseudosurface \(S^\circ \), having at most one singular point, and some spheres glued to \(S^\circ\) in a tree structure.

Let \(\operatorname{PW}(G)\) and \(\operatorname{TW}(G)\) denote the path-width and tree-width of a graph \(G\), respectively. Let \(G+H\) denote the join of two graphs \(G\) and \(H\). We show in this paper that

\(\operatorname{PW}(G + H) = \min\{|V(G)| + \operatorname{PW}(H),|V(H)| + \operatorname{PW}(G)\}\)

and

\(\operatorname{TW}(G + H) = \min\{|V(G)| + \operatorname{TW}(H), |V(H)| + \operatorname{TW}(G)\}\).

For a positive integer \(k\), a \(k\)-subdominating function of \(G = (V, E)\) is a function \(f: V \to \{-1, 1\}\) such that the sum of the function values, taken over closed neighborhoods of vertices, is at least one for at least \(k\) vertices of \(G\). The sum of the function values taken over all vertices is called the aggregate of \(f\) and the minimum aggregate amongst all \(k\)-subdominating functions of \(G\) is the \(k\)-subdomination number \(\gamma_{ks}(G)\). In the special cases where \(k = |V|\) and \(k = \lceil|V|/2\rceil\), \(\gamma_{ks}\) is respectively the signed domination number [{4}] and the majority domination number [{2}]. In this paper we characterize minimal \(k\)-subdominating functions. By determining \(\gamma_{ks}\) for paths, we give a sharp lower bound for \(\gamma_{ks}\) for trees. We also determine an upper bound for \(\gamma_{ks}\) for trees which is sharp for \(k \leq |V|/2 \).

Let \(G\) be a connected (multi)graph. We define the leaf-exchange spanning tree graph \( {T_l}\) of \(G\) as the graph with vertex set \(V_l = \{T|T \text{ is a spanning tree of } G\}\) and edge set \(E_l = \{(T, T’)|E(T)\Delta E(T’) = \{e, f\}, e \in E(T), f \in E(T’) \text{ and } e \text{ and } f \text{ are incident with a vertex } v \text{ of degree } 1 \text{ in } T \text{ and } T’\}\). \({T}(G)\) is a spanning subgraph of the so-called spanning tree graph of \(G\), and of the adjacency spanning tree graph of \(G\), which were studied by several authors. A variation on the leaf-exchange spanning tree graph appeared in recent work on basis graphs of branching greedoids. We characterize the graphs which have a connected leaf-exchange spanning tree graph and give a lower bound on the connectivity of \( {T_l}(G)\) for a \(3\)-connected graph \(G\).

The fine structure of a directed triple system of index \(\lambda\) is the vector \((c_1,c_2,\ldots,c_\lambda)\), where \(c_i\) is the number of directed triples appearing precisely \(i\) times in the system. We determine necessary and sufficient conditions for a vector to be the fine structure of a directed triple system of index \(3\) for \(v \equiv 0\) or \(1 \pmod{3}\).

Let \(p\) denote the circumference of a two-connected graph \(G\). We construct a hamiltonian cycle in \(G^2\) which contains more than \(p/2\) edges of \(G\). Using this construction we prove some properties of hamiltonian cycles in the square of \(G\).

For a connected graph \(G\) that is not a cycle, a path or a claw, let its \(k\)-iterated line graph have the diameter \(diam_k\), and the radius \(r_k\). Then \(diam_{k+1} = diam_k + 1\) for sufficiently large \(k\). Moreover, \(\{r_k\}\) also tends to infinity and the sequence \(\{diam_k – r_k – \sqrt{2\log_2 k}\}\) is bounded.