Calcul pratique du treillis de Galois d'une correspondance
Cancellation of direct products of digraphs
We investigate expressions of form A×C ≅ B×C involving direct products of digraphs. Lovász gave exact conditions on C for which it necessarily follows that A ≅ B. We are here concerned with a different aspect of cancellation. We describe exact conditions on A for which it necessarily follows that A ≅ B. In the process, we do the following: Given an arbitrary digraph A and a digraph C that admits a homomorphism onto an arc, we classify all digraphs B for which A×C ≅ B×C.
Catalan monoids, monoids of local endomorphisms, and their presentations.
Centers of directed cacti
Chaines maximales de préordres.
Characteristic for reflexive relations.
Characterization of power digraphs modulo
A power digraph modulo , denoted by , is a directed graph with as the set of vertices and as the edge set, where and are any positive integers. In this paper we find necessary and sufficient conditions on and such that the digraph has at least one isolated fixed point. We also establish necessary and sufficient conditions on and such that the digraph contains exactly two components. The primality of Fermat number is also discussed.
Characterization of Tournaments by Coned 3-Cycles
Characterizations of graphs having orientations satisfying local degree restrictions
Characterizing which Powers of Hypercubes and Folded Hyper- cubes Are Divisor Graphs
In this paper, we show that Qkn is a divisor graph, for n = 2, 3. For n ≥ 4, we show that Qkn is a divisor graph iff k ≥ n − 1. For folded-hypercube, we get FQn is a divisor graph when n is odd. But, if n ≥ 4 is even integer, then FQn is not a divisor graph. For n ≥ 5, we show that (FQn)k is not a divisor graph, where 2 ≤ k ≤ [n/2] − 1.
Ciclos de Hamilton en redes de paso conmutativo y de paso fijo.
From a natural generalization to Z2 of the concept of congruence, it is possible to define a family of 2-regular digraphs that we call commutative-step networks. Particular examples of such digraphs are the cartesian product of two directed cycles, C1 x Ch, and the fixed-step network (or 2-step circulant digraph) DN,a,b.In this paper the theory of congruences in Z2 is applied to derive three equivalent characterizations of those commutative-step networks that have a Hamiltonian cycle. Some known...
Circuit bases of strongly connected digraphs
The cycle space of a strongly connected graph has a basis consisting of directed circuits. The concept of relevant circuits is introduced as a generalization of the relevant cycles in undirected graphs. A polynomial time algorithm for the computation of a minimum weight directed circuit basis is outlined.
Circuits et arbres de circulation d'un graphe fortement connexe
Circular digraph walks, -balanced strings, lattice paths and Chebychev polynomials.
Circular distance in directed graphs
Circular distance between two vertices , of a strongly connected directed graph is the sum , where is the usual distance in digraphs. Its basic properties are studied.
Coalescence of difans and diwheels.
Coassociative grammar, periodic orbits, and quantum random walk over .
Colorations généralisées, graphes biorientés et deux ou trois choses sur François
La généralisation des nombres chromatiques de Stahl a été un premier thème de travail avec François et a abouti à l’introduction de la notion de colorations généralisées et leurs nombres chromatiques associés, notées . Cette nouvelle notion a permis d’une part, d’infirmer avec Payan une conjecture posée par Brigham et Dutton, et d’autre part, d’étendre de manière naturelle la formule de récurrence de Stahl aux nombres chromatiques . Cette relation s’exprime comme . La conjecture de Bouchet...
Colorings and nowhere-zero flows of graphs in terms of Berlekamp's switching game.
Colorings and orientations of matrices and graphs.