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 24 Next

Displaying 461 – 480 of 501

Showing per page

The Phylogeny Graphs of Doubly Partial Orders

Boram Park, Yoshio Sano (2013)

Discussiones Mathematicae Graph Theory

The competition graph of a doubly partial order is known to be an interval graph. The CCE graph and the niche graph of a doubly partial order are also known to be interval graphs if the graphs do not contain a cycle of length four and three as an induced subgraph, respectively. Phylogeny graphs are variant of competition graphs. The phylogeny graph P(D) of a digraph D is the (simple undirected) graph defined by V (P(D)) := V (D) and E(P(D)) := {xy | N+D (x) ∩ N+D(y) ¹ ⊘ } ⋃ {xy | (x,y) ∈ A(D)},...

The primitive Boolean matrices with the second largest scrambling index by Boolean rank

Yan Ling Shao, Yubin Gao (2014)

Czechoslovak Mathematical Journal

The scrambling index of an n × n primitive Boolean matrix A is the smallest positive integer k such that A k ( A T ) k = J , where A T denotes the transpose of A and J denotes the n × n all ones matrix. For an m × n Boolean matrix M , its Boolean rank b ( M ) is the smallest positive integer b such that M = A B for some m × b Boolean matrix A and b × n Boolean matrix B . In 2009, M. Akelbek, S. Fital, and J. Shen gave an upper bound on the scrambling index of an n × n primitive matrix M in terms of its Boolean rank b ( M ) , and they also characterized all primitive...

The structure of digraphs associated with the congruence x k ≡ y ( mod n )

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

Czechoslovak Mathematical Journal

We assign to each pair of positive integers n and k ≥ 2 a digraph G ( n , k ) 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 k ≡ b ( mod n ) . We investigate the structure of G ( n , k ) . In particular, upper bounds are given for the longest cycle in G ( n , k ) . We find subdigraphs of G ( n , k ) , called fundamental constituents of G ( n , k ) , for which all trees attached to cycle vertices are isomorphic.

Tournois et ordres médians pour une opinion

B. Monjardet (1973)

Mathématiques et Sciences Humaines

Dans cet article on étudie les propriétés d’ordres totaux à distance minimum d’un ensemble de tournois ; on montre, par exemple, que ces ordres contiennent l’ordre d’unanimité. On étudie la fonction f ( n , v ) maximum de la distance entre un ordre total et v tournois définis sur un ensemble à n éléments ; on donne sa valeur exacte pour v pair, un encadrement pour v impair, et sa valeur limite pour v tendant vers l’infini.

Transitive closure and transitive reduction in bidirected graphs

Ouahiba Bessouf, Abdelkader Khelladi, Thomas Zaslavsky (2019)

Czechoslovak Mathematical Journal

In a bidirected graph, an edge has a direction at each end, so bidirected graphs generalize directed graphs. We generalize the definitions of transitive closure and transitive reduction from directed graphs to bidirected graphs by introducing new notions of bipath and bicircuit that generalize directed paths and cycles. We show how transitive reduction is related to transitive closure and to the matroids of the signed graph corresponding to the bidirected graph.

Currently displaying 461 – 480 of 501