Return to search

Maximale Kantengewichte zusammenhängender Graphen

Das Gewicht einer Kante e = xy eines Graphen G = (V, E) ist definiert als Summe der Grade seiner Endpunkte und das Gewicht des Graphen als MInimum über alle Kantengewichte. Wir suchen für positive ganze Zahlen n,m und eine Grapheneigenschaft P den Wert:
w(n,m, P) := max{w(G) : |V(G)| = n, |E(G)| = m,G in P}.
Der ungarische Mathematiker Erdös formulierte 1990 auf dem Czecheslovak Symposium on Combinatorics, Graphs and Complexity die Problemstellung w(n,m, I) zu bestimmen, für die allgemeinste aller Graphenklassen I. Dieses Problem wurde zuerst teilweise von Invančo and Jendrol’ und dann endgültig von Jendrol’ and Schiermeyer gelöst.
Sei G in der Graphenklasse C genau dann wenn G zusammenhängend ist.
In dieser Arbeit werden Ansätze zur Bestimmung von w(n,m,C) vorgestellt. Im Speziellen betrachten wir Graphen mit bis zu 3n − 6 Kanten, sowie sehr dichte Graphen. Außerdem diskutieren wir einige verallgemeinerte Fragestellungen.

Identiferoai:union.ndltd.org:DRESDEN/oai:qucosa:de:qucosa:22813
Date13 June 2012
CreatorsPetzold, Maria
ContributorsSchiermeyer, Ingo, Voigt, Margit, Technische Universität Bergakademie Freiberg
Source SetsHochschulschriftenserver (HSSS) der SLUB Dresden
LanguageGerman
Detected LanguageGerman
Typedoc-type:doctoralThesis, info:eu-repo/semantics/doctoralThesis, doc-type:Text
Rightsinfo:eu-repo/semantics/openAccess

Page generated in 0.0018 seconds