Zehnpunktige kubische Graphen

An der Rechenanlage der Technischen Hochschule Wien wurden im Jahre 1966 von Gerd Baron alle zusammenhängenden kubischen Graphen mit zehn Knoten bestimmt. Dabei erhob sich die Frage, ob man diese Graphen nicht auch ohne Komputer auf einfache Art bestimmen könne. Die Struktur dieser 19 verschiedenen Graphen legte eine Klasseneinteilung nach der Zahl und Lage der auftretenden Dreiecke nahe. Diese Einteilung führt auch tatsächlich zum Ziel, wie in dieser Arbeit gezeigt werden soll.Da die Diagramme dieser Graphen von Balaban bereits in [1] und [2] veröffentlicht wurden, verzichten wir auf Abbildungen. In den erwähnten Arbeiten wird nicht beschrieben, wie die zehnpunktigen kubischen Graphen bestimmt wurden.Wir betrachten nur ungerichtete Graphen ohne Mehrfachkanten und Schlingen. IstG ein Graph, so verstehen wir unterV(G) die Knotenmenge vonG, unterE(G) die Kantenmenge vonG, und unter |G| die Kardinalzahl vonV(G). Ist weitersK ein Teilgraph vonG, so seiG — K der gesättigte TeilgraphH vonG mit der KnotenmengeV(H) = V(G) — V(K). Ein kubischer Graph ist ein regulärer Graph vom Grad drei. Offensichtlich enthält jeder kubische Graph Kreise.     

Graphen reeler Funktionen

Ohne Zusammenfassung     

Transitiv orientierbare Graphen

Ohne Zusammenfassung Vorgelegt von G. Hajós     

Kantendisjunkte Wege in Graphen

Ohne ZusammenfassungMit 1 Abbildung     

Faktorklassen in Graphen

Ohne Zusammenfassung     

Automorphismen von polyedrischen Graphen

Ohne ZusammenfassungDiese Arbeit ist durch ein Stipendium des Schweizerischen Nationalfonds unterstützt worden.     

1-Faktoren von Graphen

Ohne Zusammenfassung     

Über den Zusammenhang von Graphen,mit Anwendungen auf symmetrische Graphen

Ohne Zusammenfassung     

Graphen mit transitiver Automorphismengruppe

Ohne Zusammenfassung     

Zyklische Orientierungen endlicher bewerteter Graphen

Starting from problem 4 ofK. Wagner [2],H. Fleischner andP. D. Vestergaard [1] introduce the notion of a value-true walk in a finite, connected graph, the edges of which are valuated with nonnegative integers. Their main theorem states that the existence of such a walk is equivalent to the existence of an orientation of the edges with the following property: For every vertex the sum of the valuations of the incoming edges equals the sum of the valuations of the outgoing edges. Let us call such an orientation a cyclic one. In the present paper we study finite, valuated graphs that admit a cyclic orientation. First, we give two necessary conditions for a valuated graphG to admit a cyclic orientation concerning the stars and the bonds ofG, respectively. (The starS (v) of a vertexv is the set of all edges ofG incident withv.) Then, as the main part of the paper we give a characterization of those graphs for which the star- and the bond-condition is sufficient, respectively (for any valuation of the graph). These characterizations are in terms of constructability from trees andK ₃, respectively, as well as in terms of forbidden subgraphs.

---

---

Mit 2 Abbildungen     

Das lexikographische Produkt gerichteter Graphen

Ohne Zusammenfassung     

Minimalen-fach kantenzusammenhängende Graphen

Ohne Zusammenfassung     

Kantenprimitive Graphen vom Grad drei

A graph is called edge- (vertex-) primitive if the group of automorphisms acts as a primitive permutation group on the set of edges (vertices). It is shown that there are only four edge-primitive trivalent graphs. Three are bipartite cages; the fourth, with 102 vertices, is also vertex-primitive.     

Die chromatischen Polynome unterringfreier Graphen

Let G be a finite undirected graph without loops and multiple edges. A graph is called “unterringfrei”, if there is no induced subgraph being a cycle of length?4. This note shows that the chromatic polynomial of such a graph does only have positive integers as its roots. Conversely all polynomials with only positive integral roots are the chromatic polynomials of such graphs under the slight restriction that M(G;α)=0 implies that M(G;β)=0 for α>β?0.