On the bounded domination number of tournaments

In a simple digraph, a star of degree t is a union of t edges with a common tail. The k-domination number γ_k(G) of digraph G is the minimum number of stars of degree at most k needed to cover the vertex set. We prove that γ_k(T)=n/(k+1) when T is a tournament with n14k lg k vertices. This improves a result of Chen, Lu and West. We also give a short direct proof of the result of E. Szekeres and G. Szekeres that every n-vertex tournament is dominated by at most lg n−lglg n+2 vertices.     

A bound for the number of vertices of a polytope with applications

We prove that the number of vertices of a polytope of a particular kind is exponentially large in the dimension of the polytope. As a corollary, we prove that an n-dimensional centrally symmetric polytope with O(n) facets has {ie1-1} vertices and that the number of r-factors in a k-regular graph is exponentially large in the number of vertices of the graph provided k≥2r+1 and every cut in the graph with at least two vertices on each side has more than k/r edges.     

A lower bound for the number of intermediary rings

We give a sharp lower bound for the number of intermediary rings in normal pairs. As a consequence, the exact length of maximal chains, and a sharp lower bound for the number of overrings of Prüfer domains are obtained.     

A lower regulator bound for number fields

Lower bounds for regulators of algebraic number fields are very important for a variety of applications. Good estimates depend at least on the degree and the discriminant of the considered field. In this paper we present an improved bound which is obtained from more specific field data, e.g. the size of small T₂-values of the integers of the field. This is of considerable interest for computations in practice, for example, of fundamental units.     

Asymptotic enumeration of tournaments with a given score sequence containing a specified digraph

This paper studies the probability that a random tournament with specified score sequence contains a specified subgraph. The exact asymptotic value is found in the case that the scores are not too far from regular and the subgraph is not too large. An n‐dimensional saddle‐point method is used. As a sample application, we prove that almost all tournaments with a given score sequence (not too far from regular) have a trivial automorphism group. ©2000 John Wiley & Sons, Inc. Random Struct. Alg., 16: 47–57, 2000     

竞赛图弧色数的上界

有向图的弧色数指的是对有向图的弧进行着色, 使得所有连贯弧着不同颜色所需要的最少颜色数. 在介绍了一些相关结果的基础上, 通过确定顶点数较少的竞赛图弧色数的最大值, 说明了已有弧色数的上界虽然对一般有向图是紧的, 对竞赛图却是可以改进的.     

The number of tournaments with a unique spanning cycle

The number of tournaments T_n on n nodes with a unique spanning cycle is the (2n-6)th Fibonacci number when n ≥ 4. Another proof of this result is given based on a recursive construction of these tournaments.     

On the number of Hamiltonian cycles in tournaments

The main results assert that the minimum number of Hamiltonian bypasses in a strong tournament of order n and the minimum number of Hamiltonian cycles in a 2-connected tournament of order n increase exponentially with n. Furthermore, the number of Hamiltonian cycles in a tournament increases at least exponentially with the minimum outdegree of the tournament. Finally, for each k?1 there are infinitely many tournaments with precisely k Hamiltonian cycles.     

On the number of cycles in local tournaments

A digraph without loops, multiple arcs and directed cycles of length two is called a local tournament if the set of in-neighbors as well as the set of out-neighbors of every vertex induces a tournament. A vertex of a strongly connected digraph is called a non-separating vertex if its removal preserves the strong connectivity of the digraph in question.In 1990, Bang-Jensen showed that a strongly connected local tournament does not have any non-separating vertices if and only if it is a directed cycle. Guo and Volkmann extended this result in 1994. They determined the strongly connected local tournament with exactly one non-separating vertex. In the first part of this paper we characterize the class of strongly connected local tournaments with exactly two non-separating vertices.In the second part of the paper we consider the following problem: Given a strongly connected local tournament D of order n with at least n+2 arcs and an integer 3≤r≤n. How many directed cycles of length r exist in D? For tournaments this problem was treated by Moon in 1966 and Las Vergnas in 1975. A reformulation of the results of the first part shows that we have characterized the class of strongly connected local tournaments with exactly two directed cycles of length n−1. Among other things we show that D has at least n−r+1 directed cycles of length r for 4≤r≤n−1 unless it has a special structure. Moreover, we characterize the class of local tournaments with exactly n−r+1 directed cycles of length r for 4≤r≤n−1 which generalizes a result of Las Vergnas.     

A new upper bound for the harmonious chromatic number

A harmonious coloring of a simple graph G is a proper vertex coloring such that each pair of colors appears together on at most one edge. The harmonious chromatic number h(G) is the least number of colors in such a coloring. We obtain a new upper bound for the harmonious chromatic number of general graphs. © 1998 John Wiley & Sons, Inc. J Graph Theory 29: 257–261, 1998     

The number of bipartite tournaments with a unique given factor

We give a recursive function in order to calculate the number of all non-isomorphic bipartite tournaments containing an unique hamiltonian cycle. Using this result we determine the number of all nonisomorphic bipartite tournaments that admit an unique factor isomorphic to a given 1-diregu-lar bipartite graph.     

A bound for the Milnor number of plane curve singularities

Let f = 0 be a plane algebraic curve of degree d > 1 with an isolated singular point at 0 ∈ ?². We show that the Milnor number μ₀(f) is less than or equal to (d?1)² ? [d/2], unless f = 0 is a set of d concurrent lines passing through 0, and characterize the curves f = 0 for which μ₀(f) = (d?1)² ? [d/2].     

A better bound for the cop number of general graphs

In this note, we prove that the cop number of any n‐vertex graph G, denoted by , is at most . Meyniel conjectured . It appears that the best previously known sublinear upper‐bound is due to Frankl, who proved . © 2008 Wiley Periodicals, Inc. J Graph Theory 58: 45–48, 2008     

A lower bound for the convexity number of some graphs

Given a connected graphG, we say that a setC ?V(G) is convex inG if, for every pair of verticesx, y ∈ C, the vertex set of everyx-y geodesic inG is contained inC. The convexity number ofG is the cardinality of a maximal proper convex set inG. In this paper, we show that every pairk, n of integers with 2 ≤k ≤ n?1 is realizable as the convexity number and order, respectively, of some connected triangle-free graph, and give a lower bound for the convexity number ofk-regular graphs of ordern withn>k+1.     

A lower bound for the distance k-domination number of trees

A subset D of vertices of a graph G = (V, E) is a distance k-dominating set for G if the distance between every vertex of V ? D and D is at most k. The minimum size of a distance k-dominating set of G is called the distance k-domination number γ_k(G) of G. In this paper we prove that (2k + 1)γ_k(T) ≥ ¦V¦ + 2k ? kn₁ for each tree T = (V, E) with n₁ leafs, and we characterize the class of trees that satisfy the equality (2k + 1)γ_k(T) = ¦V¦ + 2k ? kn₁. Our results generalize those of Lemanska [4] for k = 1 and of Cyman, Lemanska and Raczek [1] for k = 2.     

A lower bound for the number of transitive perfect codes

We construct at least $\frac{1}{{8n^2 \sqrt 3 }}e^{\pi \sqrt {2n/3} } (1 + o(1))$ pairwise nonequivalent transitive extended perfect codes of length 4n as n → ∞.     

A lower bound for the equilateral number of normed spaces

We show that if the Banach-Mazur distance between an -dimensional normed space and is at most , then there exist equidistant points in . By a well-known result of Alon and Milman, this implies that an arbitrary -dimensional normed space admits at least equidistant points, where is an absolute constant. We also show that there exist equidistant points in spaces sufficiently close to , .

     

A lower bound for the interval number of a graph

The interval number i(G) of a graph G with n vertices is the lowest integer m such that G is the intersection graph of some family of sets I₁,…,I_n with every I_i being the union of at most m real intervals. In this article a lower bound for i(G) is proved followed by some considerations about the construction of graphs that are critical with respect to the interval number.