Weak k-reconstruction of Cartesian products graphs

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 graphs
Avtorji:	ID Imrich, Wilfried (Avtor) ID Zmazek, Blaž (Avtor) ID Žerovnik, Janez (Avtor)
Datoteke:	http://dx.doi.org/10.1016/S1571-0653(04)00414-7
Jezik:	Angleški jezik
Vrsta gradiva:	Članek v reviji
Tipologija:	1.12 - Objavljeni povzetek znanstvenega prispevka na konferenci
Organizacija:	PEF - Pedagoška fakulteta
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:	matematika, teorija grafov, kartezični produkt, problem rekonstrukcije, sestavljeni grafi, mathematics, graph theory, reconstruction problem, Cartesian product, composite graphs
Leto izida:	2001
Št. strani:	str. 1-4
Številčenje:	Vol. 10
PID:	20.500.12556/DKUM-51508
UDK:	519.17
COBISS.SI-ID:	13824601
ISSN pri članku:	1571-0653
NUK URN:	URN:SI:UM:DK:WBTNPHIP
Datum objave v DKUM:	10.07.2015
Število ogledov:	1447
Število prenosov:	21
Metapodatki:
Področja:	Ostalo
:	Kopiraj citat

Skupna ocena:	(0 glasov)
Vaša ocena:	Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
Objavi na:

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

Gradivo je del revije

Naslov:	Electronic notes in discrete mathematics
Založnik:	Elsevier
ISSN:	1571-0653
COBISS.SI-ID:	13803097

Sekundarni jezik

Jezik:	Slovenski jezik
Naslov:	Šibka k-rekonstrukcija kartezičnih produktov grafov
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. 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.

Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)

0 - 0 / 0

Ni komentarjev!

Nazaj