Let \(\lambda DK_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 DK_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 \leq k \leq 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 \leq n \leq 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.