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.

In \([1]\) it is proved that each \(4\)-critical plane graph contains either a \(4\)- or a \(5\)-cycle or otherwise a face of size between \(6\) and \(11\).

For nonempty graphs \(G\) and \(H\), \(H\) is said to be \(G\)-decomposable (written \(G|H\)) if \(E(H)\) can be partitioned into sets \(E_1, \ldots, E_n\) such that the subgraph induced by each \(E_i\) is isomorphic to \(G\). If \(H\) is a graph of minimum size such that \(F|H\) and \(G|H\), then \(H\) is called a least common multiple of \(F\) and \(G\). The size of such a least common multiple is denoted by \(\mathrm{lcm}(F,G)\). We show that if \(F\) and \(G\) are bipartite, then \(\mathrm{lcm}(F,G) \leq |V(F)|\cdot|V(G)|\), where equality holds if \((|V(F)|,|V(G)|) = 1\). We also determine \(\mathrm{lcm}(F,G)\) exactly if \(F\) and \(G\) are cycles or if \(F = P_m, G = K_n\), where \(n\) is odd and \((m-1,\frac{1}{2}(n-1)) = 1\), in the latter case extending a result in [{8}].

Let \(G\) be a graph. A vertex subversion strategy of \(G\), \(S\), is a set of vertices in \(G\) whose closed neighborhood is deleted from \(G\). The survival-subgraph is denoted by \(G/S\). The vertex-neighbor-integrity of \(G\), \(\mathrm{VNI}(G)\), is defined to be \(\mathrm{VNI}(G) = \displaystyle\min_{S\subseteq V(G)} \{|S| + w(G/S)\}\), where \(S\) is any vertex subversion strategy of \(G\), and \(w(G/S)\) is the maximum order of the components of \(G/S\). In this paper, we show the minimum and the maximum vertex-neighbor-integrity among all trees with any fixed order, and also show that for any integer \(l\) between the extreme values there is a tree with the vertex-neighbor-integrity \(l\).

Let \(G\) be a graph of size \(\binom{n+1}{2}\) for some integer \(n \geq 2\). Then \(G\) is said to have an ascending star subgraph decomposition if \(G\) can be decomposed into \(n\) subgraphs \(G_1, G_2, \ldots, G_n\) such that each \(G_i\) is a star of size \(i\) with \(1 \leq i \leq n\). We shall prove in this paper that a star forest with size \(\binom{n+1}{2}\) possesses an ascending star subgraph decomposition under some conditions on the number of components or the size of components.

Let \(G\) and \(H\) be connected graphs and let \(G \square H\) be the Cartesian product of \(G\) by \(H\). A lower and an upper bound for the independence number of the Cartesian product of graphs is proved for the case, where one of the factors is bipartite. Cartesian products with one factor being an odd path or an odd cycle are considered as well.

It is proved in particular that if \(S_1 + S_2\) is a largest 2-independent set of a graph \(G\), such that \(|S_2|\) is as small as possible and if \(|S_2| \leq n+2\), then \(\alpha(G \square P_{2n+1}) = (n+1)|S_1| + n|S_2|\). A similar result is shown for the Cartesian product with an odd cycle. It is finally proved that \(\alpha(C_{2k+1} \square C_{2n+1}) = k(2n+1)\), extending a result of Jha and Slutzki.

Parallel processing has been a valuable tool for improving the performance of many algorithms. Solving intractable problems is an attractive application of parallel processing. Traditionally, exhaustive search techniques have been used to find solutions to \(NP\)-complete problems. However, the performance benefit of parallelization of exhaustive search algorithms can only provide linear speedup, which is typically of little use as problem complexity increases exponentially with problem size. Genetic algorithms can be useful tools to provide satisfactory results to such problems. This paper presents a genetic algorithm that uses parallel processing in a cooperative fashion to determine mappings for the rectilinear crossing problem. Results from this genetic algorithm are presented which contradict a conjecture that has been open for over 20 years regarding the minimal crossing number for rectilinear graphs.

A balanced tournament design, \(\mathrm{BTD}(n)\), defined on a \(2n\)-set \(V\), is an arrangement of the \(\binom{2n}{2}\) distinct unordered pairs of the elements of \(V\) into an \(n \times 2n-1\) array such that:
(1) every element of \(V\) is contained in precisely one cell of each column, and
(2) every element of \(V\) is contained in at most two cells of each row.

If we can partition the columns of a \(\mathrm{BTD}(n)\) defined on \(V\) into three sets \(C_1, C_2, C_3\) of sizes \(1, n-1, n-1\) respectively such that the columns in \(C_1 \cup C_2\) form a Howell design of side \(m\) and order \(2n\), an \(\mathrm{H}(n,2n)\), and the columns in \(C_1 \cup C_3\) form an \(\mathrm{H}(n,2n)\), then the \(\mathrm{BTD}(n)\) is called partitionable. We denote a partitioned balanced tournament design of side \(n\) by \(\mathrm{PBTD}(n)\). The existence of these designs has been determined except for seven possible exceptions. In this note, we describe constructions for four of these designs. This completes the spectrum of \(\mathrm{PBTD}(n)\) for \(n\) even.

In this note we complete the table of Ramsey numbers for \(K_s\) versus the family of all \((p,q)\)-graphs for \(p \leq 8\).
Moreover, some results are obtained for the general case.

Let \(G\) be a \(2\)-connected graph of order \(n\) with connectivity \(\kappa\) and independence number \(\alpha\). In this paper, we show that if for each independent set \(S\) with \(|S| = k+1\), there are \(u,v \in S\) such that satisfying one of the following conditions:

1. \(d(u) + d(v) \geq n\); or \(|N(u) \cap N(v)| \geq \alpha\); or \(|N(u) \cup N(v)| \geq n-k\);
2. for any \(x \in \{u,v\}\), \(y \in V(G)\) and \(d(x,y) = 2\), it implies that \(\max\{d(x), d(y)\} \geq n/2\),

then \(G\) is hamiltonian. This result reveals the internal relations among several well-known sufficient conditions: \((1)\) it shows that it does not need to consider all pairs of nonadjacent or distance two vertices in \(G\); \((2)\) it makes known that for different pairs of vertices in \(G\), it permits to satisfy different conditions.

Let \(G\) be a graph of order \(p\) such that both \(G\) and \(\overline{G}\) have no isolated vertices. Let \(\Upsilon_t\) and \(\overline{\Upsilon}_t\) denote respectively the total domination number of \(G\) and \(\overline{G}\). In this paper we obtain a characterization of all graphs \(G\) for which \\(i) \(\Upsilon_t +\overline{\Upsilon}_t= p+1\) and (ii) \(\Upsilon_t + \overline{\Upsilon}_t = p\).

The bondage number \(b(G)\) of a nonempty graph \(G\) was first introduced by Fink, Jacobson, Kinch, and Roberts [3]. In their paper they conjectured that \(b(G) \leq \Delta(G)+1\) for a nonempty graph \(G\). A counterexample for this conjecture was shown in [5]. Beyond it, we show now that there doesn’t exist an upper bound of the following form: \(b(G) \leq \Delta(G)+c\) for any \(c\in\mathbb{N}\).

It is shown that if \(t > 1\) and \(u \geq 5\), then the known necessary condition for the existence of a skew Room frame of type \(t^u\), is also sufficient with the possible exception of \((u, f)\) where \(u = 5\) and \(t \in \{11, 13, 17, 19, 23, 29, 31, 41, 43\}\).

The class of \(t-sc\) graphs constitutes a new generalization of self-complementary graphs. Many \(t-sc\) graphs exhibit a stable complementing permutation. In this paper, we prove a sufficient condition for the existence of a stable complementing permutation in a \(t-sc\) graph. We also construct several infinite classes of \(t-sc\) graphs to show the stringency of our sufficient condition.

A polyhex graph is either a hexagonal system or a coronoid system. A polyhex graph \(G\) is said to be \(k\)-coverable if for any \(k\) mutually disjoint hexagons the subgraph obtained from \(G\) by deleting all these \(k\) hexagons together with their incident edges has at least one perfect matching. In this paper, a constructive criterion is given to determine whether or not a given polyhex graph is \(k\)-coverable. Furthermore, a simple method is developed which allows us to determine whether or not there exists a \(k\)-coverable polyhex graph with exactly \(h\) hexagons.

A \((k, \lambda)\)-semiframe of type \(g^u\) is a group divisible design of type \(g^u\) \((\chi, \mathcal{G}, \mathcal{B})\), in which \(\mathcal{B}\) is written as a disjoint union \(\mathcal{B} = \mathcal{P} \cup \mathcal{Q} \) where \(\mathcal{P} \) is partitioned into partial parallel classes of \(\chi\) (with respect to some \(G \in \mathcal{G}\)) and \(\mathcal{Q} \) is partitioned into parallel classes of \(\chi\). In this paper, new constructions for these designs are provided with some series of designs with \(k = 3\). Cyclic semiframes are discussed. Finally, an application of semiframes is also mentioned.

A solution of Dudeney’s round table problem is given when \(n\) is as follows:

1. \(n = pq + 1\), where \(p\) and \(q\) are odd primes.
2. \(n = p^e + 1\), where \(p\) is an odd prime.
3. \(n = p^e q^f + 1\), where \(p\) and \(q\) are distinct odd primes satisfying \(p \geq 5\) and \(q \geq 11\), and \(e\) and \(f\) are natural numbers.