Infinite families of crossing-critical graphs with prescribed average degree and crossing number

Povzetek

Širan constructed infinite families of ▫$k$▫-crossing-critical graphs for every ▫$k \ge 3$▫ and Kochol constructed such families of simple graphs for every ▫$k \ge 2$▫. Richter and Thomassen argued that, for any given ▫$k \ge 1$▫ and ▫$r \ge 6$▫, there are only finitely many simple ▫$k$▫-crossing-critical graphs with minimum degree ▫$r$▫. Salazar observed that the same argument implies such a conclusion for simple ▫$k$▫-crossing-critical graphs of prescribed average degree ▫$r > 6$▫. He established existence of infinite families of simple ▫$k$▫-crossing-critical graphs with any prescribed rational average degree ▫$r \in [4,6)$▫ for infinitely many ▫$k$▫ and asked about their existence for ▫$r \in (3,4)$▫. The question was partially settled by Pinontoan and Richter, who answered it positively for ▫$r \in (3\frac{1}{2},4)$▫. The present contribution uses two new constructions of crossing critical simple graphs along with the one developed by Pinontoan and Richter to unify these results and to answer Salazar's question by the following statement: for every rational number ▫$r \in (3,6)$▫ there exists an integer ▫$N_r$▫, such that, for any ▫$k > N_r$▫, there exists an infinite family of simple 3-connected crossing-critical graphs with average degree ▫$r$▫ and crossing number ▫$k$▫. Moreover, a universal lower bound on ▫$k$▫ applies for rational numbers in any closed interval ▫$I \subset (3,6)$▫.

Ključne besede

matematika;teorija grafov;prekrižno število;kritičen graf;prekrižno-kritičen graf;povprečna stopnja;mathematics;graph theory;crossing number;critical graph;crossing-critical graph;average degree;graph;

Podatki

Jezik:	Angleški jezik
Leto izida:	2010
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	UM FNM - Fakulteta za naravoslovje in matematiko
UDK:	519.17
COBISS:	15438169
ISSN:	0364-9024
Št. ogledov:	48
Št. prenosov:	18
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarne ključne besede:	matematika;teorija grafov;prekrižno število;kritičen graf;prekrižno-kritičen graf;povprečna stopnja;
Vrsta dela (COBISS):	Delo ni kategorizirano
Strani:	str. 139-162
Letnik:	ǂVol. ǂ65
Zvezek:	ǂiss. ǂ2
Čas izdaje:	2010
DOI:	10.1002/jgt.20470
ID:	1474841