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

Displaying 61 – 80 of 8546

Showing per page

A bound for the rank-one transient of inhomogeneous matrix products in special case

Arthur Kennedy-Cochran-Patrick, Sergeĭ Sergeev, Štefan Berežný (2019)

Kybernetika

We consider inhomogeneous matrix products over max-plus algebra, where the matrices in the product satisfy certain assumptions under which the matrix products of sufficient length are rank-one, as it was shown in [6] (Shue, Anderson, Dey 1998). We establish a bound on the transient after which any product of matrices whose length exceeds that bound becomes rank-one.

A bound on the k -domination number of a graph

Lutz Volkmann (2010)

Czechoslovak Mathematical Journal

Let G be a graph with vertex set V ( G ) , and let k ≥ 1 be an integer. A subset D ⊆ V ( G ) is called a k -dominating set if every vertex v ∈ V ( G ) - D has at least k neighbors in D . The k -domination number γ k ( G ) of G is the minimum cardinality of a k -dominating set in G . If G is a graph with minimum degree δ ( G ) ≥ k + 1 , then we prove that γ k + 1 ( G ) ≤ | V ( G ) | + γ k ( G ) 2 . In addition, we present a characterization of a special class of graphs attaining equality in this inequality.

A cancellation property for the direct product of graphs

Richard H. Hammack (2008)

Discussiones Mathematicae Graph Theory

Given graphs A, B and C for which A×C ≅ B×C, it is not generally true that A ≅ B. However, it is known that A×C ≅ B×C implies A ≅ B provided that C is non-bipartite, or that there are homomorphisms from A and B to C. This note proves an additional cancellation property. We show that if B and C are bipartite, then A×C ≅ B×C implies A ≅ B if and only if no component of B admits an involution that interchanges its partite sets.

A canonical Ramsey-type theorem for finite subsets of ℕ

Diana Piguetová (2003)

Commentationes Mathematicae Universitatis Carolinae

T. Brown proved that whenever we color 𝒫 f ( ℕ ) (the set of finite subsets of natural numbers) with finitely many colors, we find a monochromatic structure, called an arithmetic copy of an ω -forest. In this paper we show a canonical extension of this theorem; i.eẇhenever we color 𝒫 f ( ℕ ) with arbitrarily many colors, we find a canonically colored arithmetic copy of an ω -forest. The five types of the canonical coloring are determined. This solves a problem of T. Brown.

A CAT algorithm for the exhaustive generation of ice piles

Paolo Massazza, Roberto Radicioni (2010)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

We present a CAT (constant amortized time) algorithm for generating those partitions of n that are in the ice pile model IPM k (n), a generalization of the sand pile model SPM (n). More precisely, for any fixed integer k, we show that the negative lexicographic ordering naturally identifies a tree structure on the lattice IPM k (n): this lets us design an algorithm which generates all the ice piles of IPM k (n) in amortized time O(1) and in space O( n ).

A CAT algorithm for the exhaustive generation of ice piles

Paolo Massazza, Roberto Radicioni (2011)

RAIRO - Theoretical Informatics and Applications

We present a CAT (constant amortized time) algorithm for generating those partitions of n that are in the ice pile model IPM k (n), a generalization of the sand pile model SPM (n). More precisely, for any fixed integer k, we show that the negative lexicographic ordering naturally identifies a tree structure on the lattice IPM k (n): this lets us design an algorithm which generates all the ice piles of IPM k (n) in amortized time O(1) and in space O( n ).

Currently displaying 61 – 80 of 8546