All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 14 Next

Displaying 261 – 280 of 501

Showing per page

On a conjecture of quintas and arc-traceability in upset tournaments

Arthur H. Busch, Michael S. Jacobson, K. Brooks Reid (2005)

Discussiones Mathematicae Graph Theory

A digraph D = (V,A) is arc-traceable if for each arc xy in A, xy lies on a directed path containing all the vertices of V, i.e., hamiltonian path. We prove a conjecture of Quintas [7]: if D is arc-traceable, then the condensation of D is a directed path. We show that the converse of this conjecture is false by providing an example of an upset tournament which is not arc-traceable. We then give a characterization for upset tournaments in terms of their score sequences, characterize which arcs of...

On a connection of number theory with graph theory

Lawrence Somer, Michal Křížek (2004)

Czechoslovak Mathematical Journal

We assign to each positive integer n a digraph whose set of vertices is H = { 0 , 1 , ⋯ , n - 1 } and for which there is a directed edge from a ∈ H to b ∈ H if a 2 ≡ b ( m o d n ) . We establish necessary and sufficient conditions for the existence of isolated fixed points. We also examine when the digraph is semiregular. Moreover, we present simple conditions for the number of components and length of cycles. Two new necessary and sufficient conditions for the compositeness of Fermat numbers are also introduced.

On a problem of E. Prisner concerning the biclique operator

Bohdan Zelinka (2002)

Mathematica Bohemica

The symbol K ( B , C ) denotes a directed graph with the vertex set B ∪ C for two (not necessarily disjoint) vertex sets B , C in which an arc goes from each vertex of B into each vertex of C . A subdigraph of a digraph D which has this form is called a bisimplex in D . A biclique in D is a bisimplex in D which is not a proper subgraph of any other and in which B ≠ ∅ and C ≠ ∅ . The biclique digraph C → ( D ) of D is the digraph whose vertex set is the set of all bicliques in D and in which there is an arc from K ( B 1 , C 1 ) into K ( B 2 , C 2 ) if and only...

On a problem of walks

Charles Delorme, Marie-Claude Heydemann (1999)

Annales de l'institut Fourier

In 1995, F. Jaeger and M.-C. Heydemann began to work on a conjecture on binary operations which are related to homomorphisms of De Bruijn digraphs. For this, they have considered the class of digraphs G such that for any integer k , G has exactly n walks of length k , where n is the order of G . Recently, C. Delorme has obtained some results on the original conjecture. The aim of this paper is to recall the conjecture and to report where all the authors arrived.

On automorphisms of digraphs without symmetric cycles

Piotr Wójcik (1996)

Commentationes Mathematicae Universitatis Carolinae

A digraph is a symmetric cycle if it is symmetric and its underlying graph is a cycle. It is proved that if D is an asymmetric digraph not containing a symmetric cycle, then D remains asymmetric after removing some vertex. It is also showed that each digraph D without a symmetric cycle, whose underlying graph is connected, contains a vertex which is a common fixed point of all automorphisms of D .

On factorization of probability distributions over directed graphs

František Matúš, Bernhard Strohmeier (1998)

Kybernetika

Four notions of factorizability over arbitrary directed graphs are examined. For acyclic graphs they coincide and are identical with the usual factorization of probability distributions in Markov models. Relations between the factorizations over circuits are described in detail including nontrivial counterexamples. Restrictions on the cardinality of state spaces cause that a factorizability with respect to some special cyclic graphs implies the factorizability with respect to their, more simple,...

On Graph-Based Cryptography and Symbolic Computations

V. A., Ustimenko (2007)

Serdica Journal of Computing

We have been investigating the cryptographical properties of in nite families of simple graphs of large girth with the special colouring of vertices during the last 10 years. Such families can be used for the development of cryptographical algorithms (on symmetric or public key modes) and turbocodes in error correction theory. Only few families of simple graphs of large unbounded girth and arbitrarily large degree are known. The paper is devoted to the more general theory of directed graphs of large...

Currently displaying 261 – 280 of 501