Weak k-reconstruction of Cartesian products graphs

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 graphs
Authors:	ID Imrich, Wilfried (Author) ID Zmazek, Blaž (Author) ID Žerovnik, Janez (Author)
Files:	http://dx.doi.org/10.1016/S1571-0653(04)00414-7
Language:	English
Work type:	Article
Typology:	1.12 - Published Scientific Conference Contribution Abstract
Organization:	PEF - Faculty of Education
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:	matematika, teorija grafov, kartezični produkt, problem rekonstrukcije, sestavljeni grafi, mathematics, graph theory, reconstruction problem, Cartesian product, composite graphs
Year of publishing:	2001
Number of pages:	str. 1-4
Numbering:	Vol. 10
PID:	20.500.12556/DKUM-51508
UDC:	519.17
ISSN on article:	1571-0653
COBISS.SI-ID:	13824601
NUK URN:	URN:SI:UM:DK:WBTNPHIP
Publication date in DKUM:	10.07.2015
Views:	1233
Downloads:	16
Metadata:
Categories:	Misc.
:	IMRICH, Wilfried, ZMAZEK, Blaž and ŽEROVNIK, Janez, 2001, Weak k-reconstruction of Cartesian products graphs. In : Electronic notes in discrete mathematics [online]. Published Scientific Conference Contribution Abstract. 2001. p. 1–4. [Accessed 18 March 2025]. Retrieved from: http://dx.doi.org/10.1016/S1571-0653(04)00414-7 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:	Electronic notes in discrete mathematics
Publisher:	Elsevier
ISSN:	1571-0653
COBISS.SI-ID:	13803097

Secondary language

Language:	Slovenian
Title:	Šibka k-rekonstrukcija kartezičnih produktov grafov
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. 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.

Comments

Leave comment

You must log in to leave a comment.

Comments (0)

0 - 0 / 0

There are no comments!

Back