On general position sets in Cartesian products

Sandi Klavžar (Avtor), Balázs Patkós (Avtor), Gregor Rus (Avtor), Ismael G. Yero (Avtor)

Povzetek

Število splošne lege ▫${\rm gp}(G)$▫ povezanega grafa ▫$G$▫ je moč največje množice vozlišč ▫$S$▫, tako da nobena trojica različnih vozlišč iz ▫$S$▫ ne leži na skupni najkrajši poti. Takim množicam na kratko pravimo gp-množice grafa ▫$G$▫. Določeno je število splošne lege cilindrov ▫$P_r\,\square\, C_s$▫. Dokazano je, da za vse ▫$r\ge s \ge 3$▫, ▫$s\ne 4$▫ in ▫$r\ge 6$▫ velja ▫${\rm gp}(C_r\,\square\, C_s)\in \{6,7\}$▫. Dokazana je verjetnostna spodnja meja za število splošne lege kartezičnih potenc. Izpeljana je tudi formula za število gp-množic v produktih ▫$P_r\,\square\, P_s$▫, ▫$r,s\ge 2$▫.

Ključne besede

problem splošne lege;kartezični produkt grafov;poti in cikli;verjetnostne konstrukcije;točno preštevanje;general position problem;Cartesian product of graphs;paths and cycles;probabilistic constructions;exact enumeration;

Podatki

Jezik:	Angleški jezik
Leto izida:	2021
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	UM FNM - Fakulteta za naravoslovje in matematiko
Založnik:	Birkhäuser
UDK:	519.17
COBISS:	64926723
ISSN:	1422-6383
Št. ogledov:	6
Št. prenosov:	0
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Slovenski jezik
Sekundarni naslov:	Množice v splošni legi v kartezičnih produktih
Sekundarni povzetek:	The general position number ▫${\rm gp}(G)$▫ of a connected graph ▫$G$▫ is the cardinality of a largest set ▫$S$▫ of vertices such that no three distinct vertices from ▫$S$▫ lie on a common geodesic; such sets are refereed to as gp-sets of ▫$G$▫. The general position number of cylinders ▫$P_r\,\square\, C_s$▫ is deduced. It is proved that ▫${\rm gp}(C_r\,\square\, C_s)\in \{6,7\}$▫ whenever ▫$r\ge s \ge 3$▫, ▫$s\ne 4$▫, and ▫$r\ge 6$▫. A probabilistic lower bound on the general position number of Cartesian graph powers is achieved. Along the way a formula for the number of gp-sets in ▫$P_r\,\square\, P_s$▫, where ▫$r,s\ge 2$▫, is also determined.
Sekundarne ključne besede:	problem splošne lege;kartezični produkt grafov;poti in cikli;verjetnostne konstrukcije;točno preštevanje;
Vrsta dela (COBISS):	Znanstveno delo
Strani:	art. 123 (21 str.)
Letnik:	ǂVol. ǂ76
Zvezek:	ǂiss. ǂ3
Čas izdaje:	Aug. 2021
DOI:	10.1007/s00025-021-01438-x
ID:	24824352