Show simple item record

dc.contributor.authorKarimi, Majid
dc.date.accessioned2013-01-24T13:51:01Z
dc.date.available2013-01-24T13:51:01Z
dc.date.issued2013-01-24
dc.identifier.urihttp://hdl.handle.net/10464/4190
dc.description.abstractAbstract: 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.en_US
dc.language.isoengen_US
dc.publisherBrock Universityen_US
dc.subjectGraph Powers, Graph Roots, NP-completeness.en_US
dc.titleSquare Root Finding In Graphsen_US
dc.typeElectronic Thesis or Dissertationen
dc.degree.nameM.Sc. Mathematics and Statisticsen_US
dc.degree.levelMastersen_US
dc.contributor.departmentDepartment of Mathematicsen_US
dc.degree.disciplineFaculty of Mathematics and Scienceen_US
dc.embargo.termsNoneen_US
refterms.dateFOA2021-08-03T01:42:19Z


Files in this item

Thumbnail
Name:
Brock_Karimi_Majid_2012.pdf
Size:
1.662Mb
Format:
PDF

This item appears in the following Collection(s)

Show simple item record