Uniqueness of graph square roots of girth six (Q551233)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Uniqueness of graph square roots of girth six |
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| 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
0.8355408310890198
0 references
0.7880676984786987
0 references
0.7767377495765686
0 references
