20.500.12556/DKUM-49364 On subgraphs of Cartesian product graphs O podgrafih kartezičnega produkta grafov Karakterizirani so grafi, ki jih lahko predstavimo kot netrivialen podgraf kartezičnega produkta grafov. Kot posledica je pokazano, da ima vsak dvodelni graf z radijem 2, ki ne vsebuje ▫$K_{2,3}$▫, tako predstavitev. Neskončna družina bazičnih podgrafov je tudi konstruirana - dosedaj je bilo znanih le končno takih grafov. Graphs which can be represented as nontrivial subgraphs of Cartesian product graphs are characterized. As a corollary it is shown that any bipartite, ▫$K_{2,3}$▫-free graphs of radius 2 has such a representation. An infinite family of graphs which have no such representation and contain no proper representable subgraph is also constructed. Only a finite number of such graphs have been previously known. matematika teorija grafov kartezični produkt grafov podgrafi mathematics graph theory Cartesian product graphs subgraphs true false false Angleški jezik Neznan jezik Delo ni kategorizirano 2015-07-10 11:56:44 2015-07-10 11:56:44 2022-05-27 03:09:24 2019-07-10 21:28:07 1999 0 0 str. 1-9 št. 661 Vol. 37 1999 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 1318-4865 519.17 44310272 8984665 URN:SI:UM:DK:XZTTJTLB http://www.imfm.si/preprinti/PDF/00661.pdf 1 https://dk.um.si/Dokument.php?lang=slv&id=73923 Pedagoška fakulteta 0 0 0