Characterizing flag graphs and induced subgraphs of Cartesian product graphs

Povzetek

Točke zastavnega grafa ▫$\Phi(P)$▫ so verige maksimalne dolžine stopničaste delno urejene množice ▫$P$▫. Dve točki sta sosedi natanko takrat, ko se njuni maksimalni verigi razlikujeta v enem elementu. V tem delu karakteriziramo zastavne grave stopničastih delno urejenih množic in inducirane podgrafe grafov kartezičnih produktov, pri čemer zastavni grafi kot razred ležijo med induciranimi in izometričnimi podgrafi Hammingovih grafov v strukturni teoriji. Pri obeh karakterizacijah uporabimo določena označevanja povezav grafa.

Ključne besede

matematika;teorija grafov;zastavni grafi;inducirani podgrafi;označevanje povezav;grafi kartezičnih produktov;kvocientni grafi;mathematics;graph theory;flag graphs;induced subgraphs;edge-labelings;Cartesian product graphs;quotient graphs;

Podatki

Jezik:	Angleški jezik
Leto izida:	2005
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	UM FERI - Fakulteta za elektrotehniko, računalništvo in informatiko
UDK:	519.17
COBISS:	13783641
ISSN:	0167-8094
Št. ogledov:	619
Št. prenosov:	78
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Neznan jezik
Sekundarni naslov:	Karakterizacija zastavnih grafov in induciranih podgrafov grafov kartezičnih produktov
Sekundarni povzetek:	The vertices of the flag graph ▫$\Phi (P)$▫ of a graded poset ▫$P$▫ are its maximal chains. Two vertices are adjacent whenever two maximal chains differ in exactly one element. In this paper we characterize induced subgraphs of Cartesian product graphs and flag graphs of graded posets. The latter class of graphs lies between isometric and induced subgraphs of Cartesian products in the embedding structure theory. Both characterization use certain edge-labelings of graphs.
Sekundarne ključne besede:	matematika;teorija grafov;zastavni grafi;inducirani podgrafi;označevanje povezav;grafi kartezičnih produktov;kvocientni grafi;
Vrsta dela (COBISS):	Delo ni kategorizirano
Strani:	str. 283-292
Letnik:	ǂVol. ǂ21
Zvezek:	ǂno. ǂ4
Čas izdaje:	2004
ID:	1472566