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

Displaying 21 – 40 of 307

Showing per page

Rainbow Connectivity of Cacti and of Some Infinite Digraphs

Jesús Alva-Samos, Juan José Montellano-Ballesteros (2017)

Discussiones Mathematicae Graph Theory

An arc-coloured digraph D = (V,A) is said to be rainbow connected if for every pair {u, v} ⊆ V there is a directed uv-path all whose arcs have different colours and a directed vu-path all whose arcs have different colours. The minimum number of colours required to make the digraph D rainbow connected is called the rainbow connection number of D, denoted rc⃗ (D). A cactus is a digraph where each arc belongs to exactly one directed cycle. In this paper we give sharp upper and lower bounds for the...

Rainbow numbers for small stars with one edge added

Izolda Gorgol, Ewa Łazuka (2010)

Discussiones Mathematicae Graph Theory

A subgraph of an edge-colored graph is rainbow if all of its edges have different colors. For a graph H and a positive integer n, the anti-Ramsey number f(n,H) is the maximum number of colors in an edge-coloring of Kₙ with no rainbow copy of H. The rainbow number rb(n,H) is the minimum number of colors such that any edge-coloring of Kₙ with rb(n,H) number of colors contains a rainbow copy of H. Certainly rb(n,H) = f(n,H) + 1. Anti-Ramsey numbers were introduced by Erdös et al. [5] and studied in...

Rainbow Tetrahedra in Cayley Graphs

Italo J. Dejter (2015)

Discussiones Mathematicae Graph Theory

Let Γn be the complete undirected Cayley graph of the odd cyclic group Zn. Connected graphs whose vertices are rainbow tetrahedra in Γn are studied, with any two such vertices adjacent if and only if they share (as tetrahedra) precisely two distinct triangles. This yields graphs G of largest degree 6, asymptotic diameter |V (G)|1/3 and almost all vertices with degree: (a) 6 in G; (b) 4 in exactly six connected subgraphs of the (3, 6, 3, 6)-semi- regular tessellation; and (c) 3 in exactly four connected...

Ramsey numbers for trees II

Zhi-Hong Sun (2021)

Czechoslovak Mathematical Journal

Let r ( G 1 , G 2 ) be the Ramsey number of the two graphs G 1 and G 2 . For n 1 ≥ n 2 ≥ 1 let S ( n 1 , n 2 ) be the double star given by V ( S ( n 1 , n 2 ) ) = { v 0 , v 1 , ... , v n 1 , w 0 , w 1 , ... , w n 2 } and E ( S ( n 1 , n 2 ) ) = { v 0 v 1 , ... , v 0 v n 1 , v 0 w 0 , w 0 w 1 , ... , w 0 w n 2 } . We determine r ( K 1 , m - 1 , S ( n 1 , ...

Ramsey partitions and proximity data structures

Manor Mendel, Assaf Naor (2007)

Journal of the European Mathematical Society

This paper addresses two problems lying at the intersection of geometric analysis and theoretical computer science: The non-linear isomorphic Dvoretzky theorem and the design of good approximate distance oracles for large distortion.We introduce the notion of Ramsey partitions of a finite metric space, and show that the existence of good Ramsey partitions implies a solution to the metric Ramsey problem for large distortion (also known as the non-linear version of the isomorphic Dvoretzky theorem,...

Currently displaying 21 – 40 of 307