9 research outputs found
Note on the irreducible triangulations of the Klein bottle
No full textAbstractWe give the complete list of the 29 irreducible triangulations of the Klein bottle. We show how the construction of Lawrencenko and Negami, which listed only 25 such irreducible triangulations, can be modified at two points to produce the 4 additional irreducible triangulations of the Klein bottle
Thickness‐two graphs part one: New nine‐critical graphs, permuted layer graphs, and Catlin's graphs
No full text
Thickness-Two Graphs Part One: New Nine-Critical Graphs, Permuted Layer Graphs, and Catlin’s Graphs
No full textThe purpose of this paper is to offer new insight and tools toward the pursuit of the largest chromatic number in the class of thickness-two graphs. At present, the highest chromatic number known for a thickness-two graph is 9, and there is only one known color-critical 1 such graph. We introduce 40 small 9-critical thickness-two graphs, and then use a new construction, the permuted layer graphs, together with a construction of Hajós to create an infinite family of 9-critical thickness-two graphs. Finally, a non-trivial infinite subfamily of Catlin’s graphs, with directly computable chromatic numbers, is shown to have thickness two.
On the maximum number of cliques in a graph embedded in a surface
No full textThis paper studies the following question: given a surface σ and an integer n, what is the maximum number of cliques in an n-vertex graph embeddable in σ? We characterise the extremal graphs for this question, and prove that the answer is between 8(n-ω)+2 ω and 8n+5/2 2 ω+o(2 ω), where ω is the maximum integer such that the complete graph K ω embeds in σ. For the surfaces S 0, S 1, S 2, N 1, N 2, N 3 and N 4 we establish an exact answer. © 2011 David Wood.SCOPUS: ar.jinfo:eu-repo/semantics/publishe
Surface realization with the intersection edge functional
No full textDeciding realizability of a given polyhedral map on a (compact, connected) surface belongs to the hard problems in discrete geometry, from the theoretical, the algorithmic, and the practical point of view. In this paper, we present a heuristic algorithm for the realization of simplicial maps, based on the intersection edge functional. The heuristic was used to find geometric realizations in R 3 for all vertex-minimal triangulations of the orientable surfaces of genus g = 3 and g = 4. Moreover, for the first time, examples of simplicial polyhedra in R 3 of genus 5 with 12 vertices were obtained.
A programming environment to control switching networks based on STC104 packet routing chip
No full textIntroduction This work is part of a test project for the third level trigger and on-line full event reconstruction for the HERA-B experiment[1]. The high event rate (10 MHz - corresponding to the bunch crossing rate) with multiple interactions per bunch crossing will produce more than 10 7 particles per second per square centimeter in the innermost detector region. The event rate is expected to be reduced by about five orders of magnitude by a three-level trigger system. The 1 AIHENP'96 SE-142 2 Corresponding author. Tel.:+49 3762 77 350, fax: +49 3762 77 330 , e-mail: [email protected] Preprint submitted to Elsevier Preprint 11 November first and second level trigger will operate on a limited range of data, due to the hard time constraints for these systems. In the data acquisition scheme the event building is performed after the second level trigger decision. The events are then routed to the third level trigger, a
Irreducible triangulations of the once-punctured torus
No full textA triangulation of a surface with fixed topological type is called irreducible if no edge can be contracted to a vertex while remaining in the category of simplicial complexes and preserving the topology of the surface. A complete list of combinatorial structures of irreducible triangulations is made by hand for the once-punctured torus, consisting of exactly 297 non-isomorphic triangulations.Plan Andaluz de Investigación (Junta de Andalucía)Ministerio de Ciencia e Innovació
