20.500.12556/DKUM-51504 Characterizing flag graphs and induced subgraphs of Cartesian product graphs Karakterizacija zastavnih grafov in induciranih podgrafov grafov kartezičnih produktov 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. 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. 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 true false false Angleški jezik Neznan jezik Delo ni kategorizirano 2015-07-10 14:52:25 2015-07-10 14:52:25 2022-05-30 03:06:07 2019-07-11 07:20:49 2005 0 0 str. 283-292 no. 4 Vol. 21 2004 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 26073856 13783641 0167-8094 URN:SI:UM:DK:WTPK8O1J http://www.springerlink.com/openurl.asp?genre=journal&issn=0167-8094 1 https://dk.um.si/Dokument.php?lang=slv&id=76064 Fakulteta za elektrotehniko, računalništvo in informatiko 0 0 0