Square Root Finding In Graphs

Abstract: Root and root finding are concepts familiar to most branches of mathematics. In graph theory, H is a square root of G and G is the square of H if two vertices x,y have an edge in G if and only if x,y are of distance at most two in H. Graph square is a basic operation with a number of results about its properties in the literature. We study the characterization and recognition problems of graph powers. There are algorithmic and computational approaches to answer the decision problem of whether a given graph is a certain power of any graph. There are polynomial time algorithms to solve this problem for square of graphs with girth at least six while the NP-completeness is proven for square of graphs with girth at most four. The girth-parameterized problem of root fining has been open in the case of square of graphs with girth five. We settle the conjecture that recognition of square of graphs with girth 5 is NP-complete. This result is providing the complete dichotomy theorem for square root finding problem.

Name thesis:degree_name

M.Sc. Mathematics and Statistics

Level thesis:degree_level

Masters

Discipline thesis:degree_discipline

Faculty of Mathematics and Science

Department dc:contributor.department

Department of Mathematics

Grantor

Brock University

Year dc:date.issued

2013

Author dc:creator

• Karimi, Majid

• Graph Powers, Graph Roots, NP-completeness.

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/10464/4190

OAI identifier oai:identifier

oai:brocku.scholaris.ca:10464/4190