Crossing numbers of Sierpiński-like graphs

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

Abstract

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.

Keywords

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;

Data

Language:	English
Year of publishing:	2005
Typology:	1.01 - Original Scientific Article
Organization:	UL FMF - Faculty of Mathematics and Physics
UDC:	519.173
COBISS:	13783897
ISSN:	0364-9024
Views:	69
Downloads:	28
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Slovenian
Secondary title:	Prekrižna števila grafov Sierpińskega
Secondary abstract:	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.
Secondary keywords:	Teorija grafov;
URN:	URN:SI:UM:
Type (COBISS):	Not categorized
Pages:	str. 186-198
Volume:	ǂVol. ǂ50
Issue:	ǂno. ǂ3
Chronology:	2005
DOI:	10.1002/jgt.20107
ID:	1472567