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.
| Identifer | oai:union.ndltd.org:DRESDEN/oai:qucosa:de:qucosa:22813 |
| Date | 13 June 2012 |
| Creators | Petzold, Maria |
| Contributors | Schiermeyer, Ingo, Voigt, Margit, Technische Universität Bergakademie Freiberg |
| Source Sets | Hochschulschriftenserver (HSSS) der SLUB Dresden |
| Language | German |
| Detected Language | German |
| Type | doc-type:doctoralThesis, info:eu-repo/semantics/doctoralThesis, doc-type:Text |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0018 seconds