Uniqueness of graph square roots of girth six (Q551233): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
| (4 intermediate revisions by 4 users not shown) | |||
| Property / review text | |||
Summary: We prove that if two graphs of girth at least 6 have isomorphic squares, then the graphs themselves are isomorphic. This is the best possible extension of the results of Ross and Harary on trees and the results of \textit{B. Farzad, L. C. Lau, V. B. Le} and \textit{N. N. Tuy} [``Computing graph roots without short cycles,'' Proc. 26th. STACS 2009, pp. 397--408 (2009)] on graphs of girth at least 7. We also make a remark on reconstruction of graphs from their higher powers. | |||
| Property / review text: Summary: We prove that if two graphs of girth at least 6 have isomorphic squares, then the graphs themselves are isomorphic. This is the best possible extension of the results of Ross and Harary on trees and the results of \textit{B. Farzad, L. C. Lau, V. B. Le} and \textit{N. N. Tuy} [``Computing graph roots without short cycles,'' Proc. 26th. STACS 2009, pp. 397--408 (2009)] on graphs of girth at least 7. We also make a remark on reconstruction of graphs from their higher powers. / rank | |||
Normal rank | |||
| Property / Mathematics Subject Classification ID | |||
| Property / Mathematics Subject Classification ID: 05C12 / rank | |||
Normal rank | |||
| Property / Mathematics Subject Classification ID | |||
| Property / Mathematics Subject Classification ID: 05C75 / rank | |||
Normal rank | |||
| Property / zbMATH DE Number | |||
| Property / zbMATH DE Number: 5923995 / rank | |||
Normal rank | |||
| Property / zbMATH Keywords | |||
reconstruction of graphs from their higher powers | |||
| Property / zbMATH Keywords: reconstruction of graphs from their higher powers / rank | |||
Normal rank | |||
| Property / describes a project that uses | |||
| Property / describes a project that uses: nauty / rank | |||
Normal rank | |||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
| Property / arXiv ID | |||
| Property / arXiv ID: 0912.2291 / rank | |||
Normal rank | |||
| links / mardi / name | links / mardi / name | ||
Latest revision as of 15:05, 18 April 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Uniqueness of graph square roots of girth six |
scientific article |
Statements
Uniqueness of graph square roots of girth six (English)
0 references
15 July 2011
0 references
Summary: We prove that if two graphs of girth at least 6 have isomorphic squares, then the graphs themselves are isomorphic. This is the best possible extension of the results of Ross and Harary on trees and the results of \textit{B. Farzad, L. C. Lau, V. B. Le} and \textit{N. N. Tuy} [``Computing graph roots without short cycles,'' Proc. 26th. STACS 2009, pp. 397--408 (2009)] on graphs of girth at least 7. We also make a remark on reconstruction of graphs from their higher powers.
0 references
reconstruction of graphs from their higher powers
0 references
