The Library

Uniqueness of graph square roots of girth six

Tools

Adamaszek, Anna and Adamaszek, Michał. (2011) Uniqueness of graph square roots of girth six. The Electronic Journal of Combinatorics, Vol.18 (No.1). P139 . ISSN 2150-959X

Preview

PDF
WRAP_Adamaszek_Uniqueness_graph_square.pdf - Published Version - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (133Kb)

Official URL: http://www.combinatorics.org/

Abstract

We prove that if two graphs of girth atleast 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 Farzad et al. on graphs of girth at least 7. We also make a remark on reconstruction of graphs from their higher powers.

Item Type:	Journal Article
Subjects:	Q Science > QA Mathematics
Divisions:	Faculty of Science > Computer Science Faculty of Science > Mathematics
Library of Congress Subject Headings (LCSH):	Graph theory, Isomorphisms (Mathematics)
Journal or Publication Title:	The Electronic Journal of Combinatorics
Publisher:	Electronic Journal of Combinatorics
ISSN:	2150-959X
Date:	1 July 2011
Volume:	Vol.18
Number:	No.1
Page Range:	P139
Status:	Peer Reviewed
Publication Status:	Published
Funder:	Engineering and Physical Sciences Research Council (EPSRC)
Grant number:	EP/D063191/1 (EPSRC)
References:	[1] Babak Farzad, Lap Chi Lau, Van Bang Le, Nguyen Ngoc Tuy, Computing Graph Roots Without Short Cycles, Proc. 26th STACS 2009 (2009) 397-408 [2] V. I. Levenshtein, A conjecture on the reconstruction of graphs from metric balls of their vertices, Discrete Mathematics 308(5-6): 993-998 (2008) [3] V. I. Levenshtein, E.V. Konstantinova, E. Konstantinov, S. Molodtsov, Reconstruction of a graph from 2-vicinities of its vertices, Discrete Applied Mathematics 156(9): 1399- 1406 (2008) [4] B.D. McKay, The Nauty graph automorphism package, http://cs.anu.edu.au/~bdm/nauty/ [5] D. J. Ross, F. Harary, The square of a tree, Bell System Technical Journal 39 (1960), 641-647
URI:	http://wrap.warwick.ac.uk/id/eprint/38719