Upper and lower bounds of the number of additional arcs in a minimal edge 1-extension of oriented path

The following upper and lower bounds of the number of additional arcs ec(P_n) in a minimal edge 1-extension of an oriented path P_n are obtained: 1) for P_n which has ends of different types and is not isomorphic to Hamiltonian path or to orientation consisting of alternating sources and sinks, |~n/6] + 1 ^ ec(P_n) ^ n + 1; 2) for P_n with ends of equal types, |~n/4] +1 ^ ec(P_n) ^ n + 1. Keywords: minimal edge extension, path orientation, fault-tolerance. Abrosimov M. B, Razumovsky P. V. ABOUT GENERATION OF NON-ISOMOR-PHIC VERTEX k-COLORINGS. In this paper, we study the generation problem for non-isomorphic vertex and edge k-colorings of a given graph. An algorithm for generating all the non-isomorphic vertex k-colorings of a graph by the Reed - Faradzhev method without using an isomorphism testing technique is suggested. The problem of generating edge k-colorings is reduced to the problem of generating vertex k-colorings.

Keywords

Authors

References