Heegaard and regular genus of 3-manifolds with boundary.
By means of branched coverings techniques, we prove that the Heegaard genus and the regular genus of an orientable 3-manifold with boundary coincide.
Heights in finite projective space, and a problem on directed graphs.
Helly property associated with the discrete planes.
Hercules and Hydra
Hercules and Hydra, a game on rooted finite trees
Hercules versus Hidden Hydra Helper
L. Kirby and J. Paris introduced the Hercules and Hydra game on rooted trees as a natural example of an undecidable statement in Peano Arithmetic. One can show that Hercules has a “short” strategy (he wins in a primitively recursive number of moves) and also a “long” strategy (the finiteness of the game cannot be proved in Peano Arithmetic). We investigate the conflict of the “short” and “long” intentions (a problem suggested by J. Nešetřil). After each move of Hercules (trying to kill Hydra fast)...
Hereditarnia
Hereditary circuit spaces
Hereditary domination and independence parameters
For a graphical property P and a graph G, we say that a subset S of the vertices of G is a P-set if the subgraph induced by S has the property P. Then the P-domination number of G is the minimum cardinality of a dominating P-set and the P-independence number the maximum cardinality of a P-set. We show that several properties of domination, independent domination and acyclic domination hold for arbitrary properties P that are closed under disjoint unions and subgraphs.
Hereditary properties of graphs: Asymptotic enumeration, global structure, and colouring.
Hereditary properties of tournaments.
Hereditary properties of words
Let be a hereditary property of words, i.e., an infinite class of finite words such that every subword (block) of a word belonging to is also in . Extending the classical Morse-Hedlund theorem, we show that either contains at least words of length for every or, for some , it contains at most words of length for every . More importantly, we prove the following quantitative extension of this result: if has words of length then, for every , it contains at most words of length...
Hereditary properties of words
Let P be a hereditary property of words, i.e., an infinite class of finite words such that every subword (block) of a word belonging to P is also in P. Extending the classical Morse-Hedlund theorem, we show that either P contains at least n+1 words of length n for every n or, for some N, it contains at most N words of length n for every n. More importantly, we prove the following quantitative extension of this result: if P has m ≤ n words of length n then, for every k ≥ n + m, it contains at most...
Hereditary subdirectly irreducible graphs
Heterochromatic matchings in edge-colored graphs.
Heuristic and metaheuristic methods for computing graph treewidth
The notion of treewidth is of considerable interest in relation to NP-hard problems. Indeed, several studies have shown that the tree-decomposition method can be used to solve many basic optimization problems in polynomial time when treewidth is bounded, even if, for arbitrary graphs, computing the treewidth is NP-hard. Several papers present heuristics with computational experiments. For many graphs the discrepancy between the heuristic results and the best lower bounds is still very large. The...
Heuristic and metaheuristic methods for computing graph treewidth
The notion of treewidth is of considerable interest in relation to NP-hard problems. Indeed, several studies have shown that the tree-decomposition method can be used to solve many basic optimization problems in polynomial time when treewidth is bounded, even if, for arbitrary graphs, computing the treewidth is NP-hard. Several papers present heuristics with computational experiments. For many graphs the discrepancy between the heuristic results and the best lower bounds is still very large....
Heuristic search algorithms on directed trees
Hexagonal 2-complexes have a strongly convex metric.
Hexavalent -transitive graphs
Let be a finite simple undirected graph with a subgroup of the full automorphism group . Then is said to be -transitive for a positive integer , if is transitive on -arcs but not on -arcs, and -transitive if it is -transitive. Let be a stabilizer of a vertex in . Up to now, the structures of vertex stabilizers of cubic, tetravalent or pentavalent -transitive graphs are known. Thus, in this paper, we give the structure of the vertex stabilizers of connected hexavalent -transitive...