How many vertices must we delete from a graph so that it no longer contains a path \(P_k\) on \(k\) vertices? We explore this question for various special graphs (hypercubes, square lattice graphs) as well as for some general families.

A complete list is given of all finite trivalent arc-transitive connected graphs on up to \(768\) vertices, completing and extending the Foster census. Several previously undiscovered graphs appear, including one on \(448\) vertices which is the smallest arc-transitive trivalent graph having no automorphism of order 2 which reverses an arc. The graphs on the list are classified according to type (as described by Djokovic and Miller in terms of group amalgams), and were produced with the help of a parallel program which finds all normal subgroups of low index in a finitely-presented group. Further properties of each graph are also given: its girth, diameter, Hamiltonicity, and whether or not it is bipartite.

In this paper the decomposition of Dyck words into a product of Dyck prime subwords is studied. The set of Dyck words which are decomposed into \(k\) components is constructed and its cardinal number is evaluated.

For an ordered set \(W = \{w_1, w_2, \ldots, w_k\}\) of vertices and a vertex \(v\) in a graph \(G\), the representation of \(v\) with respect to \(W\) is the \(k\)-vector \(r(v|W) = (d(v, w_1), d(v, w_2), \ldots, d(v, w_k))\), where \(d(x,y)\) represents the distance between the vertices \(x\) and \(y\). The set \(W\) is a resolving set for \(G\) if distinct vertices of \(G\) have distinct representations. A resolving set containing a minimum number of vertices is called a basis for \(G\) and the number of vertices in a basis is the (metric) dimension \(\dim G\). A connected graph is unicyclic if it contains exactly one cycle. For a unicyclic graph \(G\), tight bounds for \(\dim G\) are derived. It is shown that all numbers between these bounds are attainable as the dimension of some unicyclic graph.

It is an established fact that some graph-theoretic extremal questions play an important part in the investigation of communication network vulnerability. Questions concerning the realizability of graph invariants are generalizations of the extremal problems. We define a \((p,q, \kappa,\delta)\) graph as a graph having \(p\) vertices, \(q\) edges, vertex connectivity \(\kappa\) and minimum degree \(\delta\). An arbitrary quadruple of integers \((a,b, c, d)\) is called \((p,q, \kappa, \delta)\) realizable if there is a \((p,q, \kappa, \delta)\) graph with \(p=a, q=b, \kappa=c\) and \(\delta=d\). Necessary and sufficient conditions for a quadruple to be \((p,q, \kappa, \delta)\) realizable are derived. In earlier papers, Boesch and Suffel gave necessary and sufficient conditions for \((p,q, \kappa), (p,q, \lambda), (p,4, \delta), (p, \Delta,\delta, \lambda)\) and \((p, \Delta, \delta, \kappa)\) realizability, where \(\Delta\) denotes the maximum degree for all vertices in a graph and \(\lambda\) denotes the edge connectivity of a graph.

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\).