We simplify and further develop the methods and ideas of [A. Gagarin, W. Kocay, “Embedding graphs containing \( K_5 \)-subdivisions,” Ars Combin. 64 (2002), pp. 33-49] to efficiently test embeddability of graphs on the torus. Given a non-planar graph \( G \) containing a \( K_5 \)-subdivision subgraph, we show that it is possible either to transform the \( K_5 \)-subdivision into a certain type of \( K_{3,3} \)-subdivision, or else to reduce the toroidality testing problem for \( G \) to a small constant number of planarity checks and, eventually, rearrangements of planar embeddings. It is shown how to consider efficiently only one \( K_5 \)-subdivision in the input graph \( G \) to decide whether \( G \) is embeddable on the torus. This makes it possible to detect a bigger class of toroidal and non-toroidal graphs.

A graph \( G \) is called rainbow with respect to an edge coloring if no two edges of \( G \) have the same color. Given a host graph \( H \) and a guest graph \( G \subseteq H \), an edge coloring of \( H \) is called \( G \)-anti-Ramsey if no subgraph of \( H \) isomorphic to \( G \) is rainbow. The anti-Ramsey number \( f(H, G) \) is the maximum number of colors for which there is a \( G \)-anti-Ramsey edge coloring of \( H \). In this note, we consider cube graphs \( Q_n \) as host graphs and cycles \( C_k \) as guest graphs. We prove some general bounds for \( f(Q_n, C_k) \) and give the exact values for \( n \leq 4 \).

A difference system of sets (DSS) is a collection of subsets of \(\mathbb{Z}_n\), the integers mod \(n\), with the property that each non-zero element of \(\mathbb{Z}_n\) appears at least once as the difference of elements from different sets. If there is just one set, it is called a principal DSS. DSS arise naturally in the study of systematic synchronizable codes and are studied mostly over finite fields when \(n\) is a prime power. Using only triangular numbers mod \(n\), we constructed a DSS over \(\mathbb{Z}_n\) for each positive integer \(n > 3\). Necessary and sufficient conditions are given for the existence of a principal DSS using only triangular numbers in terms of coverings of \(\{1, \ldots, n-1\}\) by finite arithmetic progressions.

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 \({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.