20.500.12556/DKUM-65356 Weak k-reconstruction of Cartesian products Šibka k-rekonstrukcija kartezičnih produktov By Ulam's conjecture every finite graph ▫$G$▫ can be reconstructed from its deck of vertex deleted subgraphs. The conjecture is still open, but many special cases have been settled. In particular, one can reconstruct Cartesian products. We consider the case of ▫$k$▫-vertex deleted subgraphs of Cartesian products and prove that one can decide whether a graph ▫$H$▫ is a ▫$k$▫-vertex deleted subgraph of a Cartesian product ▫$G$▫ with at least ▫$k+1$▫ prime factors on at least ▫$k+1$▫ vertices each, and that ▫$H$▫ uniquely determines ▫$G$▫. This extends previous works of the authors and Sims. This paper also contains a counterexample to a conjecture of MacAvaney. Po Ulamovi domnevi je mogoče vsak končen graf ▫$G$▫ rekonstruirati iz množice vseh podgrafov ▫$G$▫ brez ene točke. Znano je, da je mogoče rekonstruirati kartezične produkte. Obravnavan je soroden problem, imenovan šibka rekonstrukcija. Dokazano je, da je mogoče odločiti, ali se da dani graf ▫$H$▫ dobiti iz nekega kartezičnega produkta ▫$g$▫ z odstranitvijo ▫$k$▫ točk, če privzamemo, da ima ▫$G$▫ vsaj ▫$k+1$▫ faktorjev s po ▫$k+1$▫ točkami. V tem rimeru ▫$H$▫ enolično določa ▫$G$▫. Dan je tudi protiprimer za MacAvaneyjevo domnevo. mathematics graph theory reconstruction problem Cartesian product composite graphs matematika teorija grafov kartezični produkt problem rekonstrukcije sestavljeni grafi true false true Angleški jezik Slovenski jezik Znanstveno delo 2017-03-31 14:42:49 2017-03-31 14:43:42 2022-07-08 03:07:43 2019-07-11 15:15:36 2003 0 0 str. 273-285 št. 2 Letn. 21 2003 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 1234-3099 519.17 7487065 12632409 1234-3099 URN:SI:UM:DK:NI4OPR8W Discussiones_Mathematicae_Graph_Theory_2003_Imrich,_Zmazek,_Zerovnik_Weak_k-reconstruction_of_Cartesian_products.pdf Discussiones_Mathematicae_Graph_Theory_2003_Imrich,_Zmazek,_Zerovnik_Weak_k-reconstruction_of_Cartesian_products.pdf 1 6B6D8906B438FE665BC0810BC8ED2AB6 d27bc5c70c88c183841e09d594a43550183e0dcdf66b44f03d70bf0a3ec1a0b3 0c33b521-7c0e-11eb-bb7a-00155d0001ca https://dk.um.si/Dokument.php?lang=slv&id=110440 http://www.discuss.wmie.uz.zgora.pl/gt/index.php?doi=10.7151/dmgt.1202 1 https://dk.um.si/Dokument.php?lang=slv&id=110439 Fakulteta za strojništvo 0 0 0