Algorithms for square roots of graphs

The $n$th power$( n \geq 1)$ of a graph $G = ( V,E )$, written $G^n $, is defined to be the graph having $V$ as its vertex set with two vertices $u$, $v $ adjacent in $G^n $ if and only if there exists a path of length at most $n$ between them. Similarly, graph $H$ has an $n$th root$G$ if $G^n = H$....

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on discrete mathematics 1995-02, Vol.8 (1), p.99-118
Main Authors: YAW-LING LIN, SKIENA, S. S
Format: Article
Language:English
Subjects:
Algorithms
Combinatorics
Combinatorics. Ordered structures
Exact sciences and technology
Graph theory
Graphs
Leaves
Mathematics
Sciences and techniques of general use
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The $n$th power$( n \geq 1)$ of a graph $G = ( V,E )$, written $G^n $, is defined to be the graph having $V$ as its vertex set with two vertices $u$, $v $ adjacent in $G^n $ if and only if there exists a path of length at most $n$ between them. Similarly, graph $H$ has an $n$th root$G$ if $G^n = H$. For the case of $n = 2$, $G^2 $ is the square of $G$ and $G$ is the square root of $G^2 $. This paper presents a linear time algorithm for finding the tree square roots of a given graph and a linear time algorithm for finding the square roots of planar graphs. A polynomial time algorithm for finding the square roots of subdivision graphs, which is equivalent to the problem of the inversion of total graphs, is also presented. Further, the authors give a linear time algorithm for finding a Hamiltonian cycle in a cubic graph and prove the NP-completeness of finding the maximum cliques in powers of graphs and the chordality of powers of trees.
ISSN:0895-4801
1095-7146
DOI:10.1137/S089548019120016X