Given an integer valued weighting of all elements of a 2-connected plane
graph G with vertex set V , let c(v) denote the sum of the weight of v ∈ V and of the weights of all edges and all faces incident with v. This vertex coloring of G is proper provided that c(u) 6= c(v) for any two adjacent vertices…
A nonempty vertex set X ⊆ V(G) of a hamiltonian graph G is called an of G if every X-cycle of G (i.e. a cycle of G containing all vertices of X) is hamiltonian. The h(G) of a graph G is defined to be the smallest cardinality of an H-force set of G. In the paper the study of this parameter is introduced…
For a 3-connected planar graph G with circumference c ≥ 44 it is proved that G has a cycle of length at least [1/36]c+[20/3] through any four vertices of G.
Zusammenfassung
Gegenstand der Arbeit ist die Untersuchung asymmetrischer Strukturen in Graphen.
Dabei wird insbesondere betrachtet, inwieweit solche Strukturen in Graphen
beliebiger Größe auftreten können. Nach einem Satz von Wright sind fast alle
Graphen asymmetrisch. Auf der anderen Seite…