Search

Abstract: For positive integers , an -labeling of a digraph D is a function f from into the set of nonnegative integers such that if x is adjacent to y in D and if x is of distance two to y in D. Elements of the image of f are called labels. The -labeling problem is to determine the -number of a digraph D, which is the minimum of the maximum label used in an -labeling of D. This paper studies -numbers of digraphs. In particular, we determine -numbers of digraphs whose longest dipath is of length at most 2, and -numbers of ditrees having dipaths of length 4. We also give bounds for -numbers of bipartite digraphs whose longest dipath is of length 3. Finally, we present a linear-time algorithm for determining -numbers of ditrees whose longest dipath is of length 3. [Copyright &y& Elsevier]

Abstract: This paper is devoted to characterize permutations with forbidden patterns by using canonical reduced decompositions, which leads to bijections between Dyck paths and and , respectively. We also discuss permutations in avoiding two patterns, one of length 3 and the other of length k. These permutations produce a kind of discrete continuity between the Motzkin and the Catalan numbers. [Copyright &y& Elsevier]

Abstract: The concept of labelled stratified graph (LSG) was introduced in Ţăndăreanu (Knowledge Inform. Syst. 2(4) (2000) 438) in connection with that of knowledge base with output (KBO). The aim of this paper is to present a distinct facet of this concept. We prove several algebraic properties for LSGs and we conclude that a LSG can be used independently of a KBO. In order to realize this aim we define a partial order on the set of all LSGs over a labelled graph G, an equivalence relation on and a partial order on the factor set. The set endowed with becomes a join semilattice with greatest element. Each equivalence class contains an unique LSG, which is named distinguished representative of C. This is the least element of. Particularly we obtain the distinguished representative for the supremum of two classes (DRS) and the greatest distinguished LSG (the least LSG of the greatest element of, denoted GD). Two applications are presented, one for DRS and one for GD. Several opens problems are briefly exposed in the last section. [Copyright &y& Elsevier]