Premium
Über die Kreuzungszahl vollständiger, n ‐geteilter Graphen
Author(s) -
Harborth Heiko
Publication year - 1971
Publication title -
mathematische nachrichten
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.913
H-Index - 50
eISSN - 1522-2616
pISSN - 0025-584X
DOI - 10.1002/mana.19710480113
Subject(s) - mathematics , combinatorics , disjoint sets , complement (music) , euclidean geometry , intersection (aeronautics) , graph , intersection graph , upper and lower bounds , plane (geometry) , discrete mathematics , geometry , mathematical analysis , line graph , biochemistry , chemistry , complementation , engineering , gene , phenotype , aerospace engineering
Let K ( x 1 , x 2 , ⃛, x n ) be a graph without loops or multiple edges, the complement of which consists of n disjoint complete graphs of x 1 , x 2 , ⃛, x n vertices. In this paper a class of mappings of K ( x 1 , ⃛, x n ) onto the Euclidean plane is described. The minimum number of intersection points of edges for these mappings is determined. This number also involves an upper bound for the so‐called crossing number cr ( x 1 , ⃛, x n ), being the minimum number of intersection points of edges for all mappings of K ( x 1 , ⃛, x n ) onto the Euclidean plane (see (28)). Equality in (28) is conjectured.