Crossing numbers of Sierpiński-like graphs

Sandi Klavžar (Avtor), Bojan Mohar (Avtor)

Povzetek

Obravnavano je prekrižno število grafov Sierpińskega ▫$S(n,k)$▫ in njihovih regularizacij ▫$S^+(n,k)$▫ in ▫$S^{++}(n,k)$▫. Predstavljene so eksplicitne risbe teh grafov, ki so optimalne za ▫$S^+(n,k)$▫ in ▫$S^{++}(n,k)$▫ za vse ▫$n \ge 1$▫ in ▫$k \ge 1$▫. To sta prvi netrivialni družini grafov "fraktalnega" tipa, za katere je poznano prekrižno število.

Ključne besede

matematika;teorija grafov;risanje grafov;prekrižno število;grafi Sierpińskega;avtomorfizmi grafov;ne zaključna dela;mathematics;graf theory;graph drawing;crossing number;Sierpiński graphs;graph automorphism;

Podatki

Jezik:	Angleški jezik
Leto izida:	2005
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	UL FMF - Fakulteta za matematiko in fiziko
UDK:	519.173
COBISS:	13783897
ISSN:	0364-9024
Št. ogledov:	69
Št. prenosov:	28
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Slovenski jezik
Sekundarni naslov:	Prekrižna števila grafov Sierpińskega
Sekundarni povzetek:	The crossing number of Sierpiński graphs ▫$S(n,k)$▫ and their regularizarions ▫$S^+(n,k)$▫ and ▫$S^{++}(n,k)$▫ are studied. Drawings of these graphs are presented and proved to be optimal for ▫$S^+(n,k)$▫ and ▫$S^{++}(n,k)$▫ for every ▫$n \ge 1$▫ and ▫$k \ge 1$▫. The crossing numbers of these graphs are expressed in terms of the crossing number of ▫$K_{k+1}$▫. These are the first nontrivial families of graphs of "fractal" type whose crossing number is known.
Sekundarne ključne besede:	Teorija grafov;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Delo ni kategorizirano
Strani:	str. 186-198
Letnik:	ǂVol. ǂ50
Zvezek:	ǂno. ǂ3
Čas izdaje:	2005
DOI:	10.1002/jgt.20107
ID:	1472567