Characterizing flag graphs and induced subgraphs of Cartesian product graphs

Abstract

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.

Keywords

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;

Data

Language:	English
Year of publishing:	2005
Typology:	1.01 - Original Scientific Article
Organization:	UM FERI - Faculty of Electrical Engineering and Computer Science
UDC:	519.17
COBISS:	13783641
ISSN:	0167-8094
Views:	619
Downloads:	78
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Unknown
Secondary title:	Karakterizacija zastavnih grafov in induciranih podgrafov grafov kartezičnih produktov
Secondary abstract:	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.
Secondary keywords:	matematika;teorija grafov;zastavni grafi;inducirani podgrafi;označevanje povezav;grafi kartezičnih produktov;kvocientni grafi;
Type (COBISS):	Not categorized
Pages:	str. 283-292
Volume:	ǂVol. ǂ21
Issue:	ǂno. ǂ4
Chronology:	2004
ID:	1472566