Search

For a positive integer d, a set of points in d-dimensional Euclidean space is called almost-equidistant if for any three points from the set, some two are at unit distance. Let f(d) denote the largest size of an almost-equidistant set in d-space. It is known that f (2) = 7 , f (3) = 10 , and that the extremal almost-equidistant sets are unique. We give independent, computer-assisted proofs of these statements. It is also known that f (5) ≥ 16 . We further show that 12 ≤ f (4) ≤ 13 , f (5) ≤ 20 , 18 ≤ f (6) ≤ 26 , 20 ≤ f (7) ≤ 34 , and f (9) ≥ f (8) ≥ 24 . Up to dimension 7, our work is based on various computer searches, and in dimensions 6–9, we give constructions based on the known construction for d = 5 . For every dimension d ≥ 3 , we give an example of an almost-equidistant set of 2 d + 4 points in the d-space and we prove the asymptotic upper bound f (d) ≤ O (d 3 / 2) . [ABSTRACT FROM AUTHOR]

We explore a paradigm which ties together seemingly disparate areas in number theory, additive combinatorics, and geometric combinatorics including the classical Waring problem, the Furstenberg-Sárközy theorem on squares in sets of integers with positive density, and the study of triangles (also called 2-simplices) in finite fields. Among other results we show that if Fq is the finite field of odd order q, then every matrix in Matd(Fq),d≥2 is the sum of a certain (finite) number of orthogonal matrices, this number depending only on d, the size of the matrix, and on whether q is congruent to 1 or 3 (mod 4), but independent of q otherwise. [ABSTRACT FROM AUTHOR]

Let $${P\subset\mathbb{R}^{2}}$$ be a set of n points, of which k lie in the interior of the convex hull CH( P) of P. Let us call a triangulation T of P even (odd) if and only if all its vertices have even (odd) degree, and pseudo-even (pseudo-odd) if at least the k interior vertices have even (odd) degree. On the one hand, triangulations having all its interior vertices of even degree have one nice property; their vertices can be 3-colored, see (Heawood in Quart J Pure Math 29:270-285, , Steinberg in A source book for challenges and directions, vol 55. Elsevier, Amsterdam, pp 211-248, , Diks et al. in Lecture notes in computer science, vol 2573. Springer, Berlin, pp 138-149, ). On the other hand, odd triangulations have recently found an application in the colored version of the classic 'Happy Ending Problem' of Erdős and Szekeres, see (Aichholzer et al. in SIAM J Discrete Math 23(4):2147-2155, ). It is easy to prove that there are sets of points that admit neither pseudo-even nor pseudo-odd triangulations. In this paper we show nonetheless how to construct a set of Steiner points S = S( P) of size at most $${\frac{k}{3} + c}$$ , where c is a positive constant, such that a pseudo-even (pseudo-odd) triangulation can be constructed on $${P \cup S}$$ . Moreover, we also show that even (odd) triangulations can always be constructed using at most $${\frac{n}{3} + c}$$ Steiner points, where again c is a positive constant. Our constructions have the property that all but at most two Steiner points lie in the interior of CH( P). [ABSTRACT FROM AUTHOR]

In this paper we study the extremal type problem arising from the question: What is the maximum number ET( S) of edges that a geometric graph G on a planar point set S can have such that it does not contain empty triangles? We prove: $${{n \choose 2} - O(n \log n) \leq ET(n) \leq {n \choose 2} - \left(n - 2 + \left\lfloor \frac{n}{8} \right\rfloor \right)}$$ . [ABSTRACT FROM AUTHOR]

Let $$m\geqslant 3$$ be a positive integer, and let $$\mathbb{Z}_m$$ denote the cyclic group of residues modulo m. Furthermore, let $$R(L_m; 2)(R(L_m;\mathbb{Z}_m))$$ denote the minimum integer N such that for every function $$\Delta: \{1,2,\ldots,N\}\rightarrow \{0,1\}\,(\Delta: \{1,2,\ldots,N\}\rightarrow \mathbb{Z}_m)$$ there exist m integers $$x_1< x_2<\cdots< x_m$$ satisfying $$\sum_{i=1}{m-1}x_i< x_m$$ and $$\Delta(x_1)=\Delta(x_2)=\cdots=\Delta(x_m)$$ (and $$\sum_{i=1}^{m}\Delta(x_i)=0$$ ). It is shown that $$R(L_{m};2)=R(L_m;\mathbb{Z}_m)$$ for every odd prime m. [ABSTRACT FROM AUTHOR]

C( n, k) is a graph obtained from n-cycle $$C_n\, (v_1\cdots v_nv_1)$$ by adding edges v i v i+ k ( i = 1, 2,..., n, i + k (mod n)). There are several known results on the crossing numbers of the Cartesian products of C( n, k) ( n ≤ 7) with paths, cycles and stars. In this paper we extend these results, and show that the crossing number of the Cartesian product of C(8, 2) with P n is 8 n. [ABSTRACT FROM AUTHOR]

If H is any graph of order n with k non-trivial components, each of which contains at most one cycle, then every graph of order at least n and minimum degree at least n − k contains a subdivision of H such that only edges contained in a cycle in H are subdivided. [ABSTRACT FROM AUTHOR]

Gioan showed that the number of cycle reversing classes of totally cyclic orientations of a given graph can be calculated as an evaluation of the corresponding Tutte polynomial. We note that the concept of cycle reversing classes of orientations coincides with that of Eulerian-equivalence classes considered by Chen and Stanley, and Kochol. Based on this coincidence, we give a bijective proof of Gioan’s result. Precisely, the main result of the paper is an algorithmic bijection between the set of Eulerian-equivalence classes of totally cyclic orientations and the set of spanning trees without internally active edges. [ABSTRACT FROM AUTHOR]

We show that in every r-coloring of the edges of K n there is a monochromatic double star with at least $$\frac{n(r+1)+r-1}{r^2}$$ vertices. This result is sharp in asymptotic for r = 2 and for r≥ 3 improves a bound of Mubayi for the largest monochromatic subgraph of diameter at most three. When r-colorings are replaced by local r-colorings, our bound is $$\frac{n(r+1)+r-1}{r^2+1}$$ . [ABSTRACT FROM AUTHOR]

We prove that the P 4-transformation is one-to-one on the set of graphs with minimum degree at least 3, and if graphs G and G ' have minimum degree at least 3 then any isomorphism from the P 4-graph P 4( G) to the P 4-graph P 4( G ') is induced by a vertex-isomorphism from G to G ' unless G and G ' both belong to a special family of graphs. [ABSTRACT FROM AUTHOR]

A connected graph G is said to be factor-critical if G − ν has a perfect matching for every vertex ν of G. In this paper, the factor-critical graphs G with | V( G)| maximum matchings and with | V( G)| + 1 ones are characterized, respectively. From this, some special bicritical graphs are characterized. [ABSTRACT FROM AUTHOR]

A digraph D is called super-arc-strongly connected if the arcs of every its minimum arc-disconnected set are incident to or from some vertex in D. A digraph without any directed cycle of length 2 is called an oriented graph. Sufficient conditions for digraphs to be super-arc-strongly connected have been given by several authors. However, closely related conditions for super-arc-strongly connected oriented graphs have little attention until now. In this paper we present some minimum degree and degree sequence conditions for oriented graphs to be super-arc-strongly connected. [ABSTRACT FROM AUTHOR]

Let Γ be a distance-regular graph of diameter d ≥ 3 with c 2 > 1. Let m be an integer with 1 ≤ m ≤ d − 1. We consider the following conditions: Suppose that the condition ( SC) m holds. Then it has been known that the condition ( BB) i holds for all i with 1 ≤ i ≤ m. Similarly we can show that the condition ( CA) i holds for all i with 1 ≤ i ≤ m. In this paper we prove that if the conditions ( BB) i and ( CA) i hold for all i with 1 ≤ i ≤ m, then the condition ( SC) m holds. Applying this result we give a sufficient condition for the existence of a dual polar graph as a strongly closed subgraph in Γ. [ABSTRACT FROM AUTHOR]

Many known distance-regular graphs have extra combinatorial regularities: One of them is t-homogeneity. A bipartite or almost bipartite distance-regular graph is 2-homogeneous if the number γ i = |{ x | ∂( u, x) = ∂( v, x) = 1 and ∂( w, x) = i − 1}| ( i = 2, 3,..., d) depends only on i whenever ∂( u, v) = 2 and ∂( u, w) = ∂( v, w) = i. K. Nomura gave a complete classification of bipartite and almost bipartite 2-homogeneous distance-regular graphs. In this paper, we generalize Nomura’s results by classifying 2-homogeneous triangle-free distance-regular graphs. As an application, we show that if Γ is a distance-regular graph of diameter at least four such that all quadrangles are completely regular then Γ is isomorphic to a binary Hamming graph, the folded graph of a binary Hamming graph or the coset graph of the extended binary Golay code of valency 24. We also consider the case Γ is a parallelogram-free distance-regular graph. [ABSTRACT FROM AUTHOR]

LetD=(V,E) be a minimallyk-edge-connected simple directed graph. We prove that there is a functionf(k) such that |V|=f(k) implies |E|=2k(|V|-k). We also determine the extremal graphs whose size attains this upper bound. [ABSTRACT FROM AUTHOR]