Če je ?$G$? grad, vložen v ravnini, in sta ?$x$? in ?$y$? in njegovi vozlišči, definiramo ?$d(x,y)$? kot minimalno število točk na ?$G$?, ki jih sekajo krivulje od ?$x$? do ?$y$?. Riskin je dokazal, da je v primeru ravninskega 3-povezanega kubičnega grafa ?$G_0$? število ?$d(x,y)$? enako prekrižnemu številu grafa ?$G_0+xy$?. Vprašal je, če enako velja tudi v primeru, ko ?$G_0$? ni kubičen graf. V delu je dokazano, da to ni res, tudi če dodatno privzamemo, da je ?$G_0$? 5-povezan.

Pravice

URN

URN:NBN:SI:DOC-VLFA6YN7

COBISSID

20379431

Objavljeno

21.04.2016

Metapodatki

Citiranje

APA:

Mohar, Bojan (2006). On the crossing number of almost planar graphs. Informatica (Ljubljana), letnik 30, številka 3, str. 301-303. URN:NBN:SI:DOC-VLFA6YN7 from http://www.dlib.si

MLA:

Mohar, Bojan. "On the crossing number of almost planar graphs." Informatica (Ljubljana) letnik 30. številka 3 (2006) str. 301-303.
<http://www.dlib.si/?URN=URN:NBN:SI:DOC-VLFA6YN7>

Informatica
1977-
(Zbirni zapis)