Weak k-reconstruction of Cartesian products

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

| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

First page > Show document

Show document

Title:	Weak k-reconstruction of Cartesian products
Authors:	ID Imrich, Wilfried (Author) ID Zmazek, Blaž (Author) ID Žerovnik, Janez (Author)
Files:	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
Language:	English
Work type:	Scientific work
Typology:	1.01 - Original Scientific Article
Organization:	FS - Faculty of Mechanical Engineering
Abstract:	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.
Keywords:	mathematics, graph theory, reconstruction problem, Cartesian product, composite graphs
Publication status:	Published
Publication version:	Version of Record
Year of publishing:	2003
Number of pages:	str. 273-285
Numbering:	Letn. 21, št. 2
PID:	20.500.12556/DKUM-65356
ISSN:	1234-3099
UDC:	519.17
ISSN on article:	1234-3099
COBISS.SI-ID:	12632409
NUK URN:	URN:SI:UM:DK:NI4OPR8W
Publication date in DKUM:	31.03.2017
Views:	1558
Downloads:	462
Metadata:
Categories:	Misc.
:	IMRICH, Wilfried, ZMAZEK, Blaž and ŽEROVNIK, Janez, 2003, Weak k-reconstruction of Cartesian products. Discussiones mathematicae : Graph theory [online]. 2003. Vol. 21, no. 2, p. 273–285. [Accessed 14 April 2025]. Retrieved from: https://dk.um.si/IzpisGradiva.php?lang=eng&id=65356 Copy citation

Average score:	0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 (0 votes)
Your score:	Voting is allowed only for logged in users.
Share:

Similar works from our repository:

Similar works from other repositories:

Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Record is a part of a journal

Title:	Discussiones mathematicae : Graph theory
Shortened title:	Discuss. Math., Graph Theory
Publisher:	Technical University Press
ISSN:	1234-3099
COBISS.SI-ID:	7487065

Licences

License:	CC BY-NC-ND 4.0, Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Link:	http://creativecommons.org/licenses/by-nc-nd/4.0/
Description:	The most restrictive Creative Commons license. This only allows people to download and share the work for no commercial gain and for no other purposes.
Licensing start date:	31.03.2017

Secondary language

Language:	Slovenian
Title:	Šibka k-rekonstrukcija kartezičnih produktov
Abstract:	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.
Keywords:	matematika, teorija grafov, kartezični produkt, problem rekonstrukcije, sestavljeni grafi

Comments

Leave comment

You must log in to leave a comment.

Comments (0)

0 - 0 / 0

There are no comments!

Back