Embedding a forest in a graph.
Embedding complete ternary trees into hypercubes
We inductively describe an embedding of a complete ternary tree Tₕ of height h into a hypercube Q of dimension at most ⎡(1.6)h⎤+1 with load 1, dilation 2, node congestion 2 and edge congestion 2. This is an improvement over the known embedding of Tₕ into Q. And it is very close to a conjectured embedding of Havel [3] which states that there exists an embedding of Tₕ into its optimal hypercube with load 1 and dilation 2. The optimal hypercube has dimension ⎡(log₂3)h⎤ ( = ⎡(1.585)h⎤) or ⎡(log₂3)h⎤+1....
Embedding graphs in their complements
Embedding infinite trees into a cube of infinite dimension
Embedding -quasistars into -cubes
Embedding the polytomic tree into the -cube
Embedding trees into block graphs
Embedding trees into clique-bridge-clique graphs
Embedding vertices at points: Few bends suffice for planar graphs.
Embeddings of 2-spheres in 4-manifolds.
Embeddings of graph braid and surface groups in right-angled Artin groups and braid groups.
Embeddings of Graphs in Euclidean Spaces.
Embeddings of hamiltonian paths in faulty k-ary 2-cubes
It is well known that the k-ary n-cube has been one of the most efficient interconnection networks for distributed-memory parallel systems. A k-ary n-cube is bipartite if and only if k is even. Let (X,Y) be a bipartition of a k-ary 2-cube (even integer k ≥ 4). In this paper, we prove that for any two healthy vertices u ∈ X, v ∈ Y, there exists a hamiltonian path from u to v in the faulty k-ary 2-cube with one faulty vertex in each part.
Encadrement de l'indice de slater d'un tournoi à l'aide de ses scores
Dans cet article, nous définissons un paramètre à partir des scores d’un tournoi . Ce paramètre évalue un éloignement entre le tournoi et les tournois transitifs de même ordre. Appelant le nombre minimum d’arcs à inverser pour rendre transitif, nous montrons que l’on a . Nous déterminons ensuite des bornes sur la valeur maximum de pour les tournois à donné. Nous en déduisons enfin, en fonction du nombre de sommets de et de , un encadrement de l’indice de Slater d’un tournoi quelconque....
Encodings of cladograms and labeled trees.
Encores on cores.
End Simplicial Vertices in Path Graphs
A graph is a path graph if there is a tree, called UV -model, whose vertices are the maximal cliques of the graph and for each vertex x of the graph the set of maximal cliques that contains it induces a path in the tree. A graph is an interval graph if there is a UV -model that is a path, called an interval model. Gimbel [3] characterized those vertices in interval graphs for which there is some interval model where the interval corresponding to those vertices is an end interval. In this work, we...
End-faithful spanning trees of countable graphs with prescribed sets of rays
We prove that a countable connected graph has an end-faithful spanning tree that contains a prescribed set of rays whenever this set is countable, and we show that this solution is, in a certain sense, the best possible. This improves a result of Hahn and Širáň Theorem 1.
Endlichkeitssätze für k-kritische Graphen.
Endomorphisms of symbolic algebraic varieties
The theorem of Ax says that any regular selfmapping of a complex algebraic variety is either surjective or non-injective; this property is called surjunctivity and investigated in the present paper in the category of proregular mappings of proalgebraic spaces. We show that such maps are surjunctive if they commute with sufficiently large automorphism groups. Of particular interest is the case of proalgebraic varieties over infinite graphs. The paper intends to bring out relations between model theory,...