15. SEG-Workshop u
¨ ber
Kombinatorik, Graphentheorie und Algorithmen
HTW Dresden
24. Juni 2014
15:00-15:20
Universelle Triangulierungen von Polygonen
Ulrich Brehm
TU Dresden
Abstract
Eine abstrakte Triangulierung eines n-Ecks (im Allgemeinen mit
zus¨atzlichen inneren Ecken) heißt universell, wenn sich jede Einbettung des Randes in die Ebene auf das Innere fortsetzen l¨asst (mit
geradlinigen Kanten). Wir zeigen, dass eine Triangulierung genau
dann universell ist, wenn die graphentheoretische Distanz zwischen
Ecken des Randes im Randpolygon gleich der graphentheoretischen
Distanz in der Triangulierung ist. Wir geben eine weitere graphentheoretische Charakterisierung f¨
ur universelle Triangulierungen und
diskutieren untere und obere Schranken f¨
ur die Zahl der zus¨atzlichen
Ecken einer minimalen universellen Triangulierung in Abh¨angigkeit
von n.
15:25-15:45
The Elzinga–Hearn algorithm in strictly convex planes
Thomas Jahn
TU Chemnitz
Abstract
The ”center problem” asks for points having minimal maximum
distance to a given finite point set. Elzinga and Hearn (1972) proposed
an algorithm for this problem in the Euclidean plane which relies on
obtuseness, acuteness, and rightness of triangles. It turns out that this
algorithm can be carried over to strictly convex normed planes. For
this purpose, the above mentioned notions (e.g., the types of triangles)
have to be extended suitably to the geometry of normed planes.
1
15:50-16:10
Congruent triangles in line arrangements
Carol Zamfirescu
TU Dortmund
Abstract
We present lower and upper bounds on the maximum number of
congruent triangles in finite arrangements of ℓ lines in the Euclidean
plane, focussing on small ℓ. Denote this number by f (ℓ). We show that
f (5) = 5 and that the construction realizing this maximum is unique,
f (6) = 8, and f (7) = 14. We also discuss in detail for which integers c
there exist arrangements on ℓ lines with exactly c congruent triangles.
In parallel, we treat the case when the triangles are empty (i.e. their
interior has empty intersection with every line in the arrangement).
17:00-17:20
The generalized bivariate chromatic polynomial for special
k-partite graphs and split graphs
Melanie Gerling
Uni Kassel
Abstract
In 2003 Dohmen, P¨onitz and Tittmann introduced a generalization of the chromatic polynomial P (G; y) to the bivariate chromatic
polynomial P (G; x, y). While the definition of the usual chromatic
polynomial strictly claimes, respectively, different colours for pairwise
nonadjacent vertices, the bivariate polynomial by Dohmen, P¨onitz and
Tittmann expands this set of colours by another set without any restrictions. Let X = Y ∪ Z with Y ∩ Z = ∅ be the set of all available
colours with |X| = x and |Y | = y. By a generalized proper colouring
of G we denote a map ϕ : V → X such that for all edges {u, v} ∈ E
with ϕ(u) ∈ Y and ϕ(v) ∈ Y ϕ(u) ̸= ϕ(v) holds. In other words two
adjacent vertices may only be coloured in the same colour, if this is
chosen from Z. In the presentation we will consider the form of the
bivariate chromatic polynomial for special split graphs and complete
k-partite graphs. In addition the properties of articulation points are
utilized to compute the polynomial for the related graphs.
2
17:25-17:45
Edge colorings and forbidden rainbow subgraphs
Knut Odermann
joint work with Hanno Lefmann and Carlos Hoppen
TU Chemnitz
Abstract
Balogh (2006) considered the problem of determining for a given
number r of colors and a fixed edge r-colored graph F those n-vertex
graphs G, which admit the largest number of edge colorings with r
colors such that G does not contain F as a subgraph preserving the
fixed coloring of F . For r = 3 colors and F being a one-to-one edge
colored
( triangle,
) a so-called rainbow triangle, he showed a lower bound
n
(
)
2
of 3 2 − 1 for the maximum number of 3-colorings of n-vertex
graphs avoiding a rainbow triangle. In the talk, we present results
for the cases where the forbidden graph is either the rainbow-colored
complete graph Ks or the rainbow-colored star St .
17:50-18:10
A Fiedler-like theory for the perturbed Laplacian
Israel Rocha
TU Chemnitz
Abstract
D =
The perturbed Laplacian matrix of a graph G is defined as L
D − A, where D is any diagonal matrix and A is a weighted adjacency matrix of G. As a general outcome, we showed that the second
smallest eigenvalue for a perturbed Laplacian matrices gives similar
partition properties that the Fiedler vector gives to graph. We showed
a monotonicity theorem for the harmonic eigenfunction of the second
smallest eigenvalue of the perturbed Laplacian matrix over the points
of articulation of a graph. Also, we used the notion of Perron component for the perturbed Laplacian matrix of a graph and showed how its
second smallest eigenvalue can be characterized using this definition.
3
© Copyright 2024 ExpyDoc
