Let $\lambda D{K}_v$. denote the complete directed multigraph with $v$. vertices, where any two distinct vertices $x$. and $y$. are joined by $\lambda$. arcs $(x,y)$. and $\lambda$. arcs $(y,x)$.. By a $k$.-circuit we mean a directed cycle of length $k$.. In this paper, we consider the problem of constructing maximal packings and minimal coverings of $\lambda D{K}_v$. with $k$.-circuits. Using the leave-arcs graph of packing and the repeat-arcs graph of covering, we give a unified method for finding packings and coverings. Also, we completely solve the existence of optimal packings and coverings for $5\le k\le 14$. and any $\lambda$.

We present necessary and sufficient conditions for the decomposition of $\lambda$ times the complete directed digraph, $D_v^{\lambda }$, into each of the orientations of a $4$-cycle. In our constructions, we also give necessary and sufficient conditions for such decompositions which admit cyclic or rotational automorphisms.

In this paper, a genetic algorithm and a tabu search are investigated for the maximum satisfiability problem. When the evolutionary algorithm is hybridized with the randomized procedure G-bit [14], better performance is achieved and it even outperforms the well-known probabilistic procedure GSAT [25]. On the other hand, when the random noise strategy is introduced in the tabu search, the latter competes with GSAT with walk [27] independently of the length of the tabu list. The basic result we can argue from this study is that the robustness of a method seems to be bound to the degree of `randomness’ involved in it, but at the expense of the running time. According to the experiments, GSAT and the genetic algorithm are more powerful than tabu search in its simplest form because they incorporate more `randomness’. GSAT with random walk is even more interesting than simple GSAT for the same reason. Also, heuristic methods and local search become more efficient when a random strategy such as a noise is introduced to deviate the search from its usual rules.

A vertex $x$ of a graph $G$ resolves two vertices $u$ and $v$of $G$ if the distance from $x$ to $u$ does not equal the distance from $x$ to $v$. A set $S$ of vertices of $G$ is a resolving set for $G$ if every two distinct vertices of $G$are resolved by some vertex of $S$. The minimum cardinality of a resolving set for $G$is called the metric dimension of $G$. The problem of finding the metric dimension of a graph is formulated as an integer programming problem. It is shown how a relaxation of this problem leads to a linear programming problem and hence to a fractional version of the metric dimension of a graph. The linear programming dual of this problem is considered and the solution to the corresponding integer programming problem is called the metric independence of the graph. It is shown that the problem of deciding whether, for a given graph $G$, the metric dimension of $G$equals its metric independence is NP-complete. Trees with equal metric dimension and metric independence are characterized. The metric independence number is established for various classes of graphs.

A snake in a graph is a simple cycle without chords. A snake-in-the-box is a snake in the $n$-dimensional cube $Q_n$. Combining the methods of G. Zemor (Combinatorica 17 (1997), 287-298) and of F.I. Solov’eva (Diskret Analiz. 45 (1987), 71-76) a new upper bound for the length of a snake-in-the-box is derived for $16\le n\le 19081$.

In a graph, a set $D$ is an $n$-dominating set if for every vertex $x$, not in $D$, $x$ is adjacent to at least $n$ vertices of $D$. The $n$-domination number, ${\gamma }_n(G)$, is the order of a smallest $n$-dominating set. When this concept was first introduced by Fink and Jacobson, they asked whether there existed a function $f(n)$, such that if $G$ is any graph with minimum degree at least $n$, then ${\gamma }_n(G)<{\gamma }_{f(n)}(G)$. In this paper we show that ${\gamma }_2(G)<{\gamma }_5(G)$ for all graphs with minimum degree at least $2$. Further, this result is best possible in the sense that there exist infinitely many graphs $G$ with minimum degree at least $2$ having ${\gamma }_2(G)={\gamma }_4(G)$.

Inclusive connectivity parameters for a given vertex in a graph $G$ are measures of how close that vertex is to being a cutvertex. Thus they provide a local measure of graph vulnerability. In this paper we provide bounds on the inclusive connectivity parameters in $K_2\times G$ and inductively extend the results to a certain generalized hypercube.

In this paper, the maximum graphical structure is obtained when the number of vertices p of a connected graph G and tenacity $T(G)=T$ are given. Finally, the method of constructing the sort of graphs is also presented.

Let $G$ be a bipartite graph with bipartite sets $V_1$ and $V_2$. If $f$ is a bijective function from the vertices and edges of $G$ into the first $p+q$ positive integers, where $p$ and $q$ denote the order and size of $G$, respectively, meeting the properties that $f$ is a super edge magic labeling and if the cardinal of $V_i$ is $p_i$ for $i=1,2$, then the image of the set $V_1$ is the set of the first $p_i$ positive integers and the image of the set $V_2$ is the set of integers from $p_1+1$ up to $p$. If a bipartite graph $G$ admits an special super edge magic labeling, we say that $G$ is special super edge magic. Some properties of special super edge magic graphs are presented. However, this work is mainly devoted to the study of the relations existing between super edge magic and special super edge magic labelings.

In this note, we present necessary conditions for decomposing $\lambda K_n$ into copies of $K_{2,5}$, and show that these conditions are sufficient except for $\lambda =5$ and $n=8$, and possibly for the following cases: $\lambda =1$ and $n=40$; and $\lambda =3$ and $n=16$ or $20$.

We obtain $135$ nonisomorphic nearly Kirkman triple systems of order $18$ (the smallest order for which such a system exists), including all $119$ systems of a well-defined subclass.

In overloaded task systems, it is by definition not possible to complete all tasks by their deadlines. However, it may still be desirable to maximize the number of in-time task completions. The performance of on-line schedulers with respect to this metric is investigated here. It is shown that in general, an on-line algorithm may perform arbitrarily poorly as compared to clairvoyant (off-line) schedulers. This result holds for general task workloads where there are no constraints on task characteristics. For a variety of constrained workloads that are representative of many practical applications, however, on-line schedulers that do provide a guaranteed level of performance are presented.

We present a new algorithm for computer searches for orthogonal designs. Then we use this algorithm to find new sets of sequences with entries from $\{0,\pm a,\pm b,\pm c,\pm d\}$ on the commuting variables $a,b,c,d$ with zero autocorrelation function.

Consider the hit polynomial of the path $P_{2n}$ embedded in the complete graph $K_{2n}$. We give a combinatorial interpretation of the $n$-th Bessel polynomial in terms of a modification of this hit polynomial, called the ordered hit polynomial. Also, the first derivative of the $n$-th Bessel polynomial is shown to be the ordered hit polynomial of $P_{2n-1}$ embedded in $K_{2n}$.

In a packer-spoiler game on a graph, two players jointly construct a maximal partial $F$-packing of the graph according to some rules, where $F$ is some given graph. The packer wins if all the edges are used up and the spoiler wins otherwise. The question of which graphs are wins for which player generalizes the questions of which graphs are $F$-packable and which are randomly $F$-packable. While in general such games are NP-hard to solve, we provide partial results for $F=P_3$ and solutions for $F=2K_2$.

Let G be a $(p,q)$-graph with p vertices and q edges. An edge-labeling assignment $\text{L : E}\to \text{N}$ is a map which assigns a positive integer to each edge in E. The induced map ${\text{L}}^{+}:\text{V}\to \text{N}$ defined by ${\text{L}}^{+}\text{(v)}=\mathrm{\Sigma }\{\text{L(u,v) : for all (u,v) in E}\}$ is called the vertex sum. The edge labeling assignment is called \underline{magic} if ${\text{L}}^{+}$ is a constant map. If L is a bijection with $\text{L(E)}=\{1,2,\dots ,\text{q}\}$ and L is magic then we say L is supermagic. B. M. Stewart showed that ${\text{K}}_5$ is not supermagic and when $\text{n}\equiv 0(\mathrm{mod}4)$ , ${\text{K}}_{\text{n}}$ is not supermagic. In this paper, we exhibit supermagicness for a class of regular complete k-partite graphs.