Recent Activity
Universal highly arc transitive digraphs ★★★
Author(s): Cameron; Praeger; Wormald
An alternating walk in a digraph is a walk so that the vertex is either the head of both and or the tail of both and for every . A digraph is universal if for every pair of edges , there is an alternating walk containing both and
Keywords: arc transitive; digraph
P vs. NP ★★★★
Keywords: Complexity Class; Computational Complexity; Millenium Problems; NP; P; polynomial algorithm
F_d versus F_{d+1} ★★★
Author(s): Krajicek
Keywords: Frege system; short proof
Even vs. odd latin squares ★★★
A latin square is even if the product of the signs of all of the row and column permutations is 1 and is odd otherwise.
Keywords: latin square
Universal Steiner triple systems ★★
Author(s): Grannell; Griggs; Knor; Skoviera
Keywords: cubic graph; Steiner triple system
Monotone 4-term Arithmetic Progressions ★★
Author(s): Davis; Entringer; Graham; Simmons
Keywords: monotone arithmetic progression; permutation
The Bermond-Thomassen Conjecture ★★
Keywords: cycles
Continous analogue of Hirsch conjecture ★★
Author(s): Deza; Terlaky; Zinchenko
Average diameter of a bounded cell of a simple arrangement ★★
Author(s): Deza; Terlaky; Zinchenko
Keywords: arrangement; diameter; polytope
Drawing disconnected graphs on surfaces ★★
Author(s): DeVos; Mohar; Samal
Keywords: crossing number; surface
Matchings extend to Hamiltonian cycles in hypercubes ★★
Keywords: Hamiltonian cycle; hypercube; matching
Linear Hypergraphs with Dimension 3 ★★
Author(s): de Fraysseix; Ossona de Mendez; Rosenstiehl
Keywords: Hypergraphs
Reed's omega, delta, and chi conjecture ★★★
Author(s): Reed
For a graph , we define to be the maximum degree, to be the size of the largest clique subgraph, and to be the chromatic number of .
Keywords: coloring
Pebbling a cartesian product ★★★
Author(s): Graham
We let denote the pebbling number of a graph .
Rendezvous on a line ★★★
Author(s): Alpern
Keywords: game theory; optimization; rendezvous
Linial-Berge path partition duality ★★★
Keywords: coloring; directed path; partition
What is the smallest number of disjoint spanning trees made a graph Hamiltonian ★★
Author(s): Goldengorin
We are given a complete simple undirected weighted graph and its first arbitrary shortest spanning tree . We define the next graph and find on the second arbitrary shortest spanning tree . We continue similarly by finding on , etc. Let k be the smallest number of disjoint shortest spanning trees as defined above and let be the graph obtained as union of all disjoint trees.
Question 1. What is the smallest number of disjoint spanning trees creates a graph containing a Hamiltonian path.
Question 2. What is the smallest number of disjoint spanning trees creates a graph containing a shortest Hamiltonian path?
Questions 3 and 4. Replace in questions 1 and 2 a shortest spanning tree by a 1-tree. What is the smallest number of disjoint 1-trees creates a Hamiltonian graph? What is the smallest number of disjoint 1-trees creates a graph containing a shortest Hamiltonian cycle?
Keywords: 1-trees; cycle; Hamitonian path; spanning trees
Davenport's constant ★★★
Author(s):
For a finite (additive) abelian group , the Davenport constant of , denoted , is the smallest integer so that every sequence of elements of with length has a nontrivial subsequence which sums to zero.
Keywords: Davenport constant; subsequence sum; zero sum
Coloring and immersion ★★★
Author(s): Abu-Khzam; Langston
Keywords: coloring; complete graph; immersion
Rainbow AP(4) in an almost equinumerous coloring ★★
Author(s): Conlon
Keywords: arithmetic progression; rainbow