Weak k-reconstruction of Cartesian products

Imrich, Wilfried; Zmazek, Blaž; Žerovnik, Janez

| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Prva stran > Izpis gradiva

Izpis gradiva

Naslov:	Weak k-reconstruction of Cartesian products
Avtorji:	ID Imrich, Wilfried (Avtor) ID Zmazek, Blaž (Avtor) ID Žerovnik, Janez (Avtor)
Datoteke:	Discussiones_Mathematicae_Graph_Theory_2003_Imrich,_Zmazek,_Zerovnik_Weak_k-reconstruction_of_Cartesian_products.pdf (197,33 KB) MD5: 6B6D8906B438FE665BC0810BC8ED2AB6 http://www.discuss.wmie.uz.zgora.pl/gt/index.php?doi=10.7151/dmgt.1202
Jezik:	Angleški jezik
Vrsta gradiva:	Znanstveno delo
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	FS - Fakulteta za strojništvo
Opis:	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.
Ključne besede:	mathematics, graph theory, reconstruction problem, Cartesian product, composite graphs
Status publikacije:	Objavljeno
Verzija publikacije:	Objavljena publikacija
Leto izida:	2003
Št. strani:	str. 273-285
Številčenje:	Letn. 21, št. 2
PID:	20.500.12556/DKUM-65356
ISSN:	1234-3099
UDK:	519.17
COBISS.SI-ID:	12632409
ISSN pri članku:	1234-3099
NUK URN:	URN:SI:UM:DK:NI4OPR8W
Datum objave v DKUM:	31.03.2017
Število ogledov:	1558
Število prenosov:	459
Metapodatki:
Področja:	Ostalo
:	IMRICH, Wilfried, ZMAZEK, Blaž in ŽEROVNIK, Janez, 2003, Weak k-reconstruction of Cartesian products. Discussiones mathematicae : Graph theory [na spletu]. 2003. Vol. 21, no. 2, p. 273–285. [Dostopano 1 april 2025]. Pridobljeno s: https://dk.um.si/IzpisGradiva.php?lang=slv&id=65356 Kopiraj citat

Skupna ocena:	0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 (0 glasov)
Vaša ocena:	Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
Objavi na:

Podobna dela iz repozitorija:

Podobna dela iz ostalih repozitorijev:

Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše podrobnosti ali sproži prenos.

Gradivo je del revije

Naslov:	Discussiones mathematicae : Graph theory
Skrajšan naslov:	Discuss. Math., Graph Theory
Založnik:	Technical University Press
ISSN:	1234-3099
COBISS.SI-ID:	7487065

Licence

Licenca:	CC BY-NC-ND 4.0, Creative Commons Priznanje avtorstva-Nekomercialno-Brez predelav 4.0 Mednarodna

Povezava:	http://creativecommons.org/licenses/by-nc-nd/4.0/deed.sl
Opis:	Najbolj omejujoča licenca Creative Commons. Uporabniki lahko prenesejo in delijo delo v nekomercialne namene in ga ne smejo uporabiti za nobene druge namene.
Začetek licenciranja:	31.03.2017

Sekundarni jezik

Jezik:	Slovenski jezik
Naslov:	Šibka k-rekonstrukcija kartezičnih produktov
Opis:	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.
Ključne besede:	matematika, teorija grafov, kartezični produkt, problem rekonstrukcije, sestavljeni grafi

Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)

0 - 0 / 0

Ni komentarjev!

Nazaj