On Sparse Spanners of Weighted Graphs.
A Russell set is a set which can be written as the union of a countable pairwise disjoint set of pairs no infinite subset of which has a choice function and a Russell cardinal is the cardinal number of a Russell set. We show that if a Russell cardinal has a ternary partition (see Section 1, Definition 2) then the Russell cardinal fails to have such a partition. In fact, we prove that if a ZF-model contains a Russell set, then it contains Russell sets with ternary partitions as well as Russell...
Let G and H be two graphs. The join G ∨ H is the graph obtained by joining every vertex of G with every vertex of H. The corona G ○ H is the graph obtained by taking one copy of G and |V (G)| copies of H and joining the i-th vertex of G to every vertex in the i-th copy of H. The neighborhood corona G★H is the graph obtained by taking one copy of G and |V (G)| copies of H and joining the neighbors of the i-th vertex of G to every vertex in the i-th copy of H. The edge corona G ◇ H is the graph obtained...
Let X be a set, κ be a cardinal number and let ℋ be a family of subsets of X which covers each x ∈ X at least κ-fold. What assumptions can ensure that ℋ can be decomposed into κ many disjoint subcovers? We examine this problem under various assumptions on the set X and on the cover ℋ: among other situations, we consider covers of topological spaces by closed sets, interval covers of linearly ordered sets and covers of ℝⁿ by polyhedra and by arbitrary convex sets. We focus on...
A graph G is 2-stratified if its vertex set is partitioned into two classes (each of which is a stratum or a color class), where the vertices in one class are colored red and those in the other class are colored blue. Let F be a 2-stratified graph rooted at some blue vertex v. An F-coloring of a graph is a red-blue coloring of the vertices of G in which every blue vertex v belongs to a copy of F rooted at v. The F-domination number is the minimum number of red vertices in an F-coloring of G. In...
The (directed) distance from a vertex to a vertex in a strong digraph is the length of a shortest - (directed) path in . The eccentricity of a vertex of is the distance from to a vertex furthest from in . The radius rad is the minimum eccentricity among the vertices of and the diameter diam is the maximum eccentricity. A central vertex is a vertex with eccentricity and the subdigraph induced by the central vertices is the center . For a central vertex in a strong digraph...
2010 Mathematics Subject Classification: 05C50.We say that a regular graph G of order n and degree r і 1 (which is not the complete graph) is strongly regular if there exist non-negative integers t and q such that |SiЗSj| = t for any two adjacent vertices i and j, and |SiЗSj| = q for any two distinct non-adjacent vertices i and j, where Sk denotes the neighborhood of the vertex k. Let l1 = r, l2 and l3 be the distinct eigenvalues of a connected strongly regular graph. Let m1 = 1, m2 and m3 denote...
In his book on unsolved problems in number theory [1] R. K. Guy asks whether for every natural l there exists with the following property: for every and any n elements of a group such that the product of any two of them is different from the unit element of the group, there exist l of the such that for and . In this note we answer this question in the affirmative in the first non-trivial case when l=3 and the group is abelian, proving the following result.