2013/11/04 by Rebecca Robinson, Robinson, Rebecca, Graham Farr +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #Graph Labeling and Dimension Problems #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1311.0574
22 pages, 4 figures
arxiv created 2013/11/04 · openalex publication_date 2013/11/04 · arxiv updated 2013/11/05 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
Practical algorithms for solving the Subgraph Homeomorphism Problem are known for only a few small pattern graphs: among these are the wheel graphs with four, five, six, and seven spokes. The length and difficulty of the proofs leading to these algorithms increase greatly as the size of the pattern graph increases. Proving a result for the wheel with six spokes requires extensive case analysis on many small graphs, and even more such analysis is needed for the wheel with seven spokes. This paper describes algorithms and programs used to automate the generation and testing of the graphs that arise as cases in these proofs. The main algorithm given may be useful in a more general context, for developing other characterizations of SHP-related properties.