Uniqueness of graph square roots of girth six

zbMATH Open1222.05038arXiv0912.2291MaRDI QIDQ551233FDOQ551233

Authors: Anna Adamaszek, Michał Adamaszek 

Publication date: 15 July 2011

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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

Full work available at URL: https://arxiv.org/abs/0912.2291

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• scientific article; zbMATH DE number 6027233
• Complexity of finding graph roots with girth conditions
• Large-girth roots of graphs
• scientific article; zbMATH DE number 3865328
• Large-girth roots of graphs

zbMATH Keywords

reconstruction of graphs from their higher powers

Mathematics Subject Classification ID

Distance in graphs (05C12) Structural characterization of families of graphs (05C75)

Cited In (11)

• Title not available (Why is that?)
• Parameterized algorithms for finding square roots
• Graphs with six distinct matching roots
• Finding cactus roots in polynomial time
• Finding cactus roots in polynomial time
• Edge ideals of squares of trees
• On the maximum number of independent elements in configurations of points and lines
• Computing square roots of trivially perfect and threshold graphs
• A linear kernel for finding square roots of almost planar graphs
• Finding cut-vertices in the square roots of a graph
• Faster computing of graph square roots with girth at least six

Uses Software

• nauty

This page was built for publication: Uniqueness of graph square roots of girth six

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q551233)