All regular multigraphs of even order and high degree are 1-factorable.
All Tight Descriptions of 3-Stars in 3-Polytopes with Girth 5
Lebesgue (1940) proved that every 3-polytope P5 of girth 5 has a path of three vertices of degree 3. Madaras (2004) refined this by showing that every P5 has a 3-vertex with two 3-neighbors and the third neighbor of degree at most 4. This description of 3-stars in P5s is tight in the sense that no its parameter can be strengthened due to the dodecahedron combined with the existence of a P5 in which every 3-vertex has a 4-neighbor. We give another tight description of 3-stars in P5s: there is a vertex...
Almost Abelian regular dessins d'enfants
A regular dessin d'enfant, in this paper, will be a pair (S,β), where S is a closed Riemann surface and β: S → ℂ̂ is a regular branched cover whose branch values are contained in the set {∞,0,1}. Let Aut(S,β) be the group of automorphisms of (S,β), that is, the deck group of β. If Aut(S,β) is Abelian, then it is known that (S,β) can be defined over ℚ. We prove that, if A is an Abelian group and Aut(S,β) ≅ A ⋊ ℤ₂, then (S,β) is also definable over ℚ. Moreover, if A ≅ ℤₙ, then we provide explicitly...
Almost all graphs with 2. 522 edges are not 3-colorable.
Almost all trees have an even number of independent sets.
Almost every bipartite graph has not two vertices of minimum degree
Almost every tree function is independent
Almost product evaluation of Hankel determinants.
Almost Self-Complementary 3-Uniform Hypergraphs
It is known that self-complementary 3-uniform hypergraphs on n vertices exist if and only if n is congruent to 0, 1 or 2 modulo 4. In this paper we define an almost self-complementary 3-uniform hypergraph on n vertices and prove that it exists if and only if n is congruent to 3 modulo 4. The structure of corresponding complementing permutation is also analyzed. Further, we prove that there does not exist a regular almost self-complementary 3-uniform hypergraph on n vertices where n is congruent...
Almost Tight Upper Bounds for Lower Envelopes in Higher Dimensions.
Almost-Rainbow Edge-Colorings of Some Small Subgraphs
Let f(n, p, q) be the minimum number of colors necessary to color the edges of Kn so that every Kp is at least q-colored. We improve current bounds on these nearly “anti-Ramsey” numbers, first studied by Erdös and Gyárfás. We show that [...] , slightly improving the bound of Axenovich. We make small improvements on bounds of Erdös and Gyárfás by showing [...] and for all even n ≢ 1(mod 3), f(n, 4, 5) ≤ n− 1. For a complete bipartite graph G= Kn,n, we show an n-color construction to color the edges...
Alon-Babai-Suzuki's conjecture related to binary codes in nonmodular version.
Alpha-critical hypergraphs
Alspach's problem: The case of Hamilton cycles and 5-cycles.
Alternating connectivity of digraphs
Alternating connectivity of tournaments
Alternating cycles and realizations of a degree sequence
Alternating, pattern-avoiding permutations.
Altitude of wheels and wheel-like graphs
An edge-ordering of a graph G=(V, E) is a one-to-one mapping f:E(G)→{1, 2, ..., |E(G)|}. A path of length k in G is called a (k, f)-ascent if f increases along the successive edges forming the path. The altitude α(G) of G is the greatest integer k such that for all edge-orderings f, G has a (k, f)-ascent. In our paper we give exact values of α(G) for all helms and wheels. Furthermore, we use our result to obtain altitude for graphs that are subgraphs of helms.
Amalgamation over uniform matroids