Characterizing posets for which their natural transit functions coincide

Boštjan Brešar (Avtor), Manoj Changat (Avtor), Sandi Klavžar (Avtor), Joseph Mathews (Avtor), Antony Mathews (Avtor), Prasanth G. Narasimha-Shenoi (Avtor)

Povzetek

Standardna tranzitna funkcija delno urejene množice ▫$P$▫ je funkcija ▫$T_P$▫, ki vsakemu paru primerljivih elementov priredi interval med njima, za neprimerljiva elementa ▫$x,y$▫ pa je ▫$T_P(x,y) = \{x,y\}$▫. Na tri načine, tudi s prepovedanimi delno urejenimi podmnožicami, okarakteriziramo tiste delno urejene množice, v katerih standardna tranzitna funkcija sovpada s tranzitno funkcijo najkrajših poti njenega grafa pokritij-neprimerljivosti.

Ključne besede

matematika;teorija grafov;tranzitna funkcija;rangirana delno urejena množica;temeljni graf;geodetski interval;interval induciranih poti;mathematics;graph theory;transit function;ranked poset;underlying graph;geodesic interval;induced-path interval;

Podatki

Jezik:	Angleški jezik
Leto izida:	2009
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	UL FMF - Fakulteta za matematiko in fiziko
UDK:	519.17
COBISS:	15155289
ISSN:	1855-3966
Matična publikacija:	Ars mathematica contemporanea
Št. ogledov:	65
Št. prenosov:	7
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Slovenski jezik
Sekundarni naslov:	Karakterizacija delno urejenih množic, katerih naravne tranzitne funkcije sovpadajo
Sekundarni povzetek:	The standard poset transit function of a poset ▫$P$▫ is a function ▫$T_P$▫ that assigns to a pair of comparable elements the interval between them, while ▫$T_P(x,y) = {x,y}$▫ for a pair ▫$x$▫, ▫$y$▫ of incomparable elements. Posets in which the standard poset transit function coincides with the shortest-path transit function of its cover-incomparability graph are characterized in three ways, in particular with forbidden subposets.
Sekundarne ključne besede:	matematika;teorija grafov;tranzitna funkcija;rangirana delno urejena množica;temeljni graf;geodetski interval;interval induciranih poti;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Delo ni kategorizirano
Strani:	str. 27-33
Letnik:	ǂVol. ǂ2
Zvezek:	ǂno. ǂ1
Čas izdaje:	2009
ID:	67709