Characterizing posets for which their natural transit functions coincide

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

Abstract

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.

Keywords

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;

Data

Language:	English
Year of publishing:	2009
Typology:	1.01 - Original Scientific Article
Organization:	UL FMF - Faculty of Mathematics and Physics
UDC:	519.17
COBISS:	15155289
ISSN:	1855-3966
Parent publication:	Ars mathematica contemporanea
Views:	65
Downloads:	7
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Slovenian
Secondary title:	Karakterizacija delno urejenih množic, katerih naravne tranzitne funkcije sovpadajo
Secondary abstract:	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.
Secondary keywords:	matematika;teorija grafov;tranzitna funkcija;rangirana delno urejena množica;temeljni graf;geodetski interval;interval induciranih poti;
URN:	URN:SI:UM:
Type (COBISS):	Not categorized
Pages:	str. 27-33
Volume:	ǂVol. ǂ2
Issue:	ǂno. ǂ1
Chronology:	2009
ID:	67709