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.

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.