Let $G$ be a finite $4$-regular cyclically $2k$-edge-connected simple graph for some integer $k\ge 1$. Let $E(k)$ be a set of $k$ independent edges in $G$ and $(E_1,E_2)$ be a partition of $E(k)$. We consider when there exists a $2$-factor in $G$ which excludes all edges of $E_1$, and includes all the edges of $E_2$. A complete characterization is provided.

If an edge-disjoint decomposition of a complete graph of order $n$ into copies of a $3$-star (i.e., the graph $K_{1,3}$ on $4$ vertices) is taken, and if these $3$-stars can be paired up in three distinct ways to form a graph on $6$ vertices consisting of a $4$-cycle with two opposite pendant edges, such that:
(1) in each of the three pairings, there exists a metamorphosis into a $4$-cycle system; (2) taking precisely those $4$-cycles formed from the two pendant edges from each pair of $3$-stars, in each of the three metamorphoses, we again have a $4$-cycle system of the complete graph, then this is called a complete set of metamorphoses from paired $3$-stars into $4$-cycles.

We show that such a complete set of metamorphoses from paired $3$-stars into $4$-cycles exists if and only if the order of the complete graph is $1$ or $9(\mathrm{mod}24)$, and greater than $9$.

Let $G$ be a connected graph of order $n\ge 3$ and size $m$, and let $f:E(G)\to {\mathbb{Z}}_n$ be an edge labeling of $G$. Define an induced vertex labeling $f^{\prime }:V(G)\to {\mathbb{Z}}_n$ in terms of $f$ by $f^{\prime }(v)=\sum _{u\in N(v)}f(uv)$, where the sum is computed in ${\mathbb{Z}}_n$. If $f^{\prime }$ is one-to-one, then $f$ is called a modular edge-graceful labeling and $G$ is a modular edge-graceful graph. It is known that no connected graph of order $n\ge 3$ with $n\equiv 2(\mathrm{mod}4)$ is modular edge-graceful. A 1991 conjecture states that every tree of order $n$ where $n\not\equiv 2(\mathrm{mod}4)$ is modular edge-graceful. In this work, we show that this conjecture is true and furthermore that a nontrivial connected graph of order $n$ is modular edge-graceful if and only if $n\not\equiv 2(\mathrm{mod}4)$. The modular edge-gracefulness $\text{meg}(G)$ of a connected graph $G$ of order $n\ge 3$ is the smallest integer $k\ge n$ for which there exists an edge labeling $f:E(G)\to {\mathbb{Z}}_k$ such that the induced vertex labeling $f^{\prime }:V(G)\to {\mathbb{Z}}_k$ is one-to-one. It is shown that $\text{meg}(G)=n+1$ for every connected graph $G$ that is not modular edge-graceful.

A dominating set is a vertex subset $D$ of a graph $G$ such that each vertex of $G$ is either in $D$ or adjacent to a vertex in $D$. The domination number, $\gamma (G)$, is the minimum cardinality of a dominating set of a graph $G$. In this paper, we will investigate the domination number of Fibonacci cubes. We firstly study the degree sequence of the Fibonacci cubes. Then, a lower bound for the domination number of Fibonacci cube of order $n$ is obtained, and the exact value of the domination number of Fibonacci cubes of order at most $8$ is determined.

Let $L(m,n)$ be the largest integer such that, if each symbol in an $m\times n$ rectangle occurs at most $L(m,n)$ times, then the array must have a transversal. We improve the lower bound to $L(m,n)\ge \lfloor \frac{m(n–m+1)–1}{m–1}\rfloor$ for $m>1$. Then we show that sporadically $L(m,n)<\lfloor \frac{mn–1}{m–1}\rfloor$ in the range $m\le n\le m^2–3m+3$. Define $n_0(m)$ to be the smallest integer $z$ such that if $n\ge z$ then $L(m,n)=\lfloor \frac{mn–1}{m–1}\rfloor$. We improve $n_0(m)$ from $O(m^3)$ to $O(m^{2.5})$. Finally, we determine $L(4,n)$ for all $n$.

In [1], we showed that for $v\equiv 1$ or $3(\mathrm{mod}6)$, there is an equitable $k$-edge coloring of $K_v$ that does not admit any polychromatic $STS(v)$, when $k=2,3$, and $v–2$. In this paper, we extend the results to all feasible values of $k$, where $2\le k\le v–2$.

A Costas Latin square of order $n$ is a set of $n$ disjoint Costas arrays of the same order. Costas Latin squares are studied here from both a construction and classification point of view. A complete classification is carried out up to order $27$. In this range, we verify the conjecture that there is no Costas Latin square for any odd order $n\ge 3$. Various other related combinatorial structures are also considered, including near Costas Latin squares (which are certain packings of near Costas arrays) and Vatican Costas squares.

Let $G=(V,E)$ be an undirected graph and let $\pi =\{V_1,V_2,\dots ,V_k\}$ be a partition of the vertices $V$ of $G$ into $k$ blocks $V_i$. From this partition one can construct the following digraph $D(\pi )=(\pi ,E(\pi ))$, the vertices of which correspond one-to-one with the $k$ blocks $V_i$ of $\pi$, and there is an arc from $V_i$ to $V_j$ if every vertex in $V_j$ is adjacent to at least one vertex in $V_i$, that is, $V_i$ dominates $V_j$. We call the digraph $D(\pi )$ the domination digraph of $\pi$. A triad is one of the 16 digraphs on three vertices having no loops or multiple arcs. In this paper we study the algorithmic complexity of deciding if an arbitrary graph $G$ has a given digraph as one of its domination digraphs, and in particular, deciding if a given triad is one of its domination digraphs. This generalizes results for the domatic number.

A Roman dominating function on a graph $G$ is a function $f:V(G)\to \{0,1,2\}$ such that every vertex $u$ with $f(u)=0$ is adjacent to a vertex $v$ with $f(v)=2$. The weight of a Roman dominating function $f$ is the value $f(V(G))=\sum _{u\in V(G)}f(u)$. A Roman dominating function $f$ is an independent Roman dominating function if the set of vertices for which $f$ assigns positive values is independent. The independent Roman domination number $i_R(G)$ of $G$ is the minimum weight of an independent Roman dominating function of $G$.

We show that if $T$ is a tree of order $n$, then $i_R(T)\le \frac{4n}{5}$, and characterize the class of trees for which equality holds. We present bounds for $i_R(G)$ in terms of the order, maximum and minimum degree, diameter, and girth of $G$. We also present Nordhaus-Gaddum inequalities for independent Roman domination numbers.

Let $M(b,n)$ be the complete multipartite graph with $b$ parts $B_0,\dots ,B_{b-1}$ of size $n$. A $4$-cycle system of $M(b,n)$ is said to be a $frame$ if the $4$-cycles can be partitioned into sets $S_1,\dots ,S_z$ such that for $1\le j\le z$, $S_j$ induces a $2$-factor of $M(b,n)\setminus B_i$ for some $i\in {\mathbb{Z}}_b$. The existence of a $C_4$-frame of $M(b,n)$ has been settled when $n=4$ [6]. In this paper, we completely settle the existence question of a $C_4$-frame of $M(b,n)$ for all $b\ne 2$ and $n$.

A subset $A$ of vertices of a graph $G$ is a $k$-dominating set if every vertex not in $A$ has at least $k$ neighbors in $A$ and a $k$-star-forming set if every vertex not in $A$ forms with $k$ vertices of $A$ a not necessarily induced star $K_{1,k}$. The maximum cardinalities of a minimal $k$-dominating set and of a minimal $k$-star-forming set of $G$ are respectively denoted by ${\mathrm{\Gamma }}_k(G)$ and ${\text{SF}}_k(G)$. We determine upper bounds on ${\mathrm{\Gamma }}_k(G)$ and ${\text{SF}}_k(G)$ and describe the structure of the extremal graphs attaining them.

Clatworthy described the eleven group divisible designs with three groups, block size four, and replication number at most 10. With these in mind one might ask: Can each of these designs be generalized in natural ways? In two previous papers the existence of natural generalizations of four of these designs were settled. Here we essentially settle the existence of natural generalizations of five of the remaining seven Clatworthy designs.

A complete solution is obtained for the possible number of common entries between two Latin squares of different given orders. This intersection problem assumes the entries of the smaller square are also entries of the larger, and that, for comparison, the smaller square is overlayed on the larger. However, these extra restrictions do not affect the solution, apart from one small example.

Let $G=(V,E)$ be a graph. A subset $S$ of $V$ is called an $equivalenceset$ if every component of the induced subgraph $(S)$ is complete. In this paper, starting with the concept of equivalence set as a seed property, we form an inequality chain of six parameters, which we call the $equivalencechain$ of $G$. We present several basic results on these parameters and problems for further investigation.

It has been known for some time that the Higman-Sims graph can be decomposed into the disjoint union of two Hoffman-Singleton graphs. In this paper, we establish that the Higman-Sims graph can be edge decomposed into the disjoint union of 5 double-Petersen graphs, each on 20 vertices. It is shown that, in fact, this can be achieved in 36,960 distinct ways. It is also shown that these different ways fall into a single orbit under the automorphism group $\text{HS}$ of the graph.

Recently, Graves, Pisanski, and Watkins have determined the growth rates of Bilinski diagrams of one-ended, 3-connected, edge-transitive planar maps. The computation depends solely on the edge-symbol $(p,q;k,l)$ that was introduced by B. Gr\”unbaum and G. C. Shephard in their classification of such planar tessellations. We present a census of such tessellations in which we describe some of their properties, such as whether the edge-transitive planar tessellation is vertex- or face-transitive, self-dual, bipartite, or Eulerian. In particular, we order such tessellations according to the growth rate and count the number of tessellations in each subclass.

We give general lower bounds and upper bounds on the maximum degree $\mathrm{\Delta }(G)$ of a $3_t$-critical graph $G$ in terms of the order of $G$. We also establish tighter sharp lower bounds on $\mathrm{\Delta }(G)$ in terms of the order of $G$ for several families of $3_t$-critical graphs, such as crown-graphs, claw-free graphs, and graphs with independence number $\alpha (G)=2$.

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\le 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,\dots ,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 $LadderGraph$ $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 $\varphi (G)$, is the cardinality of a smallest decycling set in $G$. We obtain sharp bounds on the value of the Cartesian product $\varphi (G\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{K}_2)$ and determine its value in the case where $G$ is the grid graph $P_m\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{P}_n$, for all $m,n\ge 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(\mathrm{mod}36)$, into truncated octahedra if and only if $v\equiv 1\text{ or }64(\mathrm{mod}72)$, and into truncated cubes if and only if $v\equiv 1\text{ or }64(\mathrm{mod}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,\dots ,q\}$ is a bijective function. For a vertex $v\in V(G)$, the induced vertex labeling of $G$ is a function $f^{\ast }(V)=\sum f(uv)$ for all $uv\in E(G)$. We say $f^{\ast }(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\ge 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 $g(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 $g(n,k)$ are determined.

Let $G$ be a connected graph and let $U$ be a set of vertices in $G$. A $minimalU-tree$ is a subtree $T$ of $G$ that contains $U$ and has the property that every vertex of $V(T)–U$ is a cut-vertex of $⟨V(T)⟩$. The $monophonicinterval$ of $U$ is the collection of all vertices of $G$ that lie on some minimal $U$-tree. A set $S$ of vertices of $G$ is $m_k$-$convex$ if it contains the monophonic interval of every $k$-subset $U$ of vertices of $S$. Thus $S$ is $m_2$-convex if and only if it is $m$-convex.

In this paper, we consider three local convexity properties with respect to $m_3$-convexity and characterize the graphs having either property.

Let $G$ and $H$ be graphs on $n+2$ vertices $\{u_1,u_2,\dots ,u_n,x,y\}$ such that $G–u_i\cong H–u_i$, for $i=1,2,\dots ,n$. Recently, Ramachandran, Monikandan, and Balakumar have shown in a sequence of two papers that if $n\ge 9$, then $|\epsilon (H)–\epsilon (G)|\le 1$. In this paper, we present a simpler proof of their theorem, using a counting lemma.