We give a new proof of the sufficiency of Landau’s conditions for a non-decreasing sequence of integers to be the score sequence of a tournament. The proof involves jumping down a total order on sequences satisfying Landau’s conditions and provides a \(O(n^2)\) algorithm that can be used to construct a tournament whose score sequence is any in the total order. We also compare this algorithm with two other algorithms that jump along this total order, one jumping down and one jumping up.

For graphs \( G \) and \( H \), \( H \) is said to be \( G \)-saturated if it does not contain a subgraph isomorphic to \( G \), but for any edge \( e \in H^c \), the complement of \( H \), \( H + e \), contains a subgraph isomorphic to \( G \). The minimum number of edges in a \( G \)-saturated graph on \( n \) vertices is denoted \( \text{sat}(n, G) \). While digraph saturation has been considered with the allowance of multiple arcs and \(2\)-cycles, we address the restriction to oriented graphs. First, we prove that for any oriented graph \( D \), there exist \( D \)-saturated oriented graphs, and hence show that \( \text{sat}(n, D) \), the minimum number of arcs in a \( D \)-saturated oriented graph on \( n \) vertices, is well defined for sufficiently large \( n \). Additionally, we determine \( \text{sat}(n, D) \) for some oriented graphs \( D \), and examine some issues unique to oriented graphs.

In this paper, we look at families \(\{G_n\}\) of graphs (for \(n > 0\)) for which the number of perfect matchings of \(G_n\) is the \(n\)th term in a sequence of generalized Fibonacci numbers. A one-factor of a graph is a set of edges forming a spanning one-regular subgraph (a perfect matching). The generalized Fibonacci numbers are the integers produced by a two-term homogeneous linear recurrence from given initial values. We explore the construction of such families of graphs, using as our motivation the \emph{Ladder Graph} \(L_n\); it is well-known that \(L_n\) has exactly \(F_{n+1}\) perfect matchings, where \(F_n\) is the traditional Fibonacci sequence, defined by \(F_1 = F_2 = 1\), and \(F_{n+1} = F_n + F_{n-1}\).

A graph is singular if the zero eigenvalue is in the spectrum of its \(0-1\) adjacency matrix \(A\). If an eigenvector belonging to the zero eigenspace of \(A\) has no zero entries, then the singular graph is said to be a core graph. A \((\kappa, \tau)\)-regular set is a subset of the vertices inducing a \(\kappa\)-regular subgraph such that every vertex not in the subset has \(\tau\) neighbors in it. We consider the case when \(\kappa = \tau\), which relates to the eigenvalue zero under certain conditions. We show that if a regular graph has a \((\kappa, \kappa)\)-regular set, then it is a core graph. By considering the walk matrix, we develop an algorithm to extract \((\kappa, \kappa)\)-regular sets and formulate a necessary and sufficient condition for a graph to be Hamiltonian.

A decycling set in a graph \( G \) is a set \( D \) of vertices such that \( G – D \) is acyclic. The decycling number of \( G \), denoted \( \phi(G) \), is the cardinality of a smallest decycling set in \( G \). We obtain sharp bounds on the value of the Cartesian product \( \phi(G \square K_2) \) and determine its value in the case where \( G \) is the grid graph \( P_m \square P_n \), for all \( m, n \geq 2 \).

We prove that the complete graph \( K_v \) can be decomposed into truncated tetrahedra if and only if \( v \equiv 1 \text{ or } 28 \pmod{36} \), into truncated octahedra if and only if \( v \equiv 1 \text{ or } 64 \pmod{72} \), and into truncated cubes if and only if \( v \equiv 1 \text{ or } 64 \pmod{72} \).

Global routing in VLSI (very large scale integration) design is one of the most challenging discrete optimization problems in computational theory and practice. In this paper, we present a polynomial time algorithm for the global routing problem based on integer programming formulation with a theoretical approximation bound. The algorithm ensures that all routing demands are satisfied concurrently, and the overall cost is approximately minimized.

We provide both serial and parallel implementation as well as develop several heuristics used to improve the quality of the solution and reduce running time. We provide computational results on two sets of well-known benchmarks and show that, with a certain set of heuristics, our new algorithms perform extremely well compared with other integer-programming models.

In 1956, Ryser gave a necessary and sufficient condition for a partial Latin rectangle to be completable to a Latin square. In 1990, Hilton and Johnson showed that Ryser’s condition could be reformulated in terms of Hall’s Condition for partial Latin squares. Thus, Ryser’s Theorem can be interpreted as saying that any partial Latin rectangle \( R \) can be completed if and only if \( R \) satisfies Hall’s Condition for partial Latin squares.

We define Hall’s Condition for partial Sudoku squares and show that Hall’s Condition for partial Sudoku squares gives a criterion for the completion of partial Sudoku rectangles that is both necessary and sufficient. In the particular case where \( n = pq \), \( p \mid r \), \( q \mid s \), the result is especially simple, as we show that any \( r \times s \) partial \((p, q)\)-Sudoku rectangle can be completed (no further condition being necessary).

Let \( G \) be a \((p, q)\)-graph. Suppose an edge labeling of \( G \) given by \( f: E(G) \to \{1, 2, \ldots, q\} \) is a bijective function. For a vertex \( v \in V(G) \), the induced vertex labeling of \( G \) is a function \( f^*(V) = \sum f(uv) \) for all \( uv \in E(G) \). We say \( f^*(V) \) is the vertex sum of \( V \). If, for all \( v \in V(G) \), the vertex sums are equal to a constant (mod \( k \)) where \( k \geq 2 \), then we say \( G \) admits a Mod(\( k \))-edge-magic labeling, and \( G \) is called a Mod(\( k \))-edge-magic graph. In this paper, we show that (i) all maximal outerplanar graphs (or MOPs) are Mod(\( 2 \))-EM, and (ii) many Mod(\( 3 \))-EM labelings of MOPs can be constructed (a) by adding new vertices to a MOP of smaller size, or (b) by taking the edge-gluing of two MOPs of smaller size, with a known Mod(\( 3 \))-EM labeling. These provide us with infinitely many Mod(\( 3 \))-EM MOPs. We conjecture that all MOPs are Mod(\( 3 \))-EM.

Let \(\gamma(n, k)\) be the maximum number of colors for the vertices of the cube graph \(Q_n\), such that each subcube \(Q_k\) contains all colors. Some exact values of \(\gamma(n, k)\) are determined.