| 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: | 1744 |
|---|
| Downloads: | 636 |
|---|
| Metadata: |    |
|---|
| Categories: | Misc.
|
|---|
|
:
|
Copy citation |
|---|
| | | | Average score: | (0 votes) |
|---|
| Your score: | Voting is allowed only for logged in users. |
|---|
| Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
