20.500.12556/DKUM-51508 Weak k-reconstruction of Cartesian products graphs Šibka k-rekonstrukcija kartezičnih produktov grafov 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. 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. matematika teorija grafov kartezični produkt problem rekonstrukcije sestavljeni grafi mathematics graph theory reconstruction problem Cartesian product composite graphs true true false Angleški jezik Slovenski jezik Članek v reviji 2015-07-10 14:52:40 2015-07-10 14:52:40 2024-03-05 14:36:38 2019-07-11 07:20:56 2001 0 0 str. 1-4 Vol. 10 Nov. 2001 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 13803097 13824601 1571-0653 URN:SI:UM:DK:WBTNPHIP http://dx.doi.org/10.1016/S1571-0653(04)00414-7 1 https://dk.um.si/Dokument.php?lang=slv&id=76068 Pedagoška fakulteta 0 0 0