Jezik: | Angleški jezik |
---|---|
Leto izida: | 2001 |
Tipologija: | 1.03 - Kratki znanstveni prispevek |
Organizacija: | UM FS - Fakulteta za strojništvo |
UDK: | 519.17 |
COBISS: | 13824601 |
ISSN: | 1571-0653 |
Št. ogledov: | 26 |
Št. prenosov: | 34 |
Ocena: | 0 (0 glasov) |
Metapodatki: |
Sekundarni jezik: | Slovenski jezik |
---|---|
Sekundarni naslov: | Šibka k-rekonstrukcija kartezičnih produktov grafov |
Sekundarni povzetek: | 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. |
Sekundarne ključne besede: | Teorija grafov; |
URN: | URN:SI:UM: |
Vrsta dela (COBISS): | Delo ni kategorizirano |
Strani: | str. 297-300 |
Zvezek: | ǂVol. ǂ10 |
Čas izdaje: | Nov. 2001 |
DOI: | 10.1016/S1571-0653(04)00414-7 |
ID: | 1472585 |