Paulusma, D. (2011) 'On finding paths passing through specified vertices.', Working Paper. Durham University.
We consider undirected finite graphs that have no loops and no multiple edges. A graph is denoted G = (VG, EG), where VG is the set of vertices and EG is the set of edges. A graph containment problem is to decide whether one graph can be modified into some other graph by using a number of specified graph operations. For example, by allowing any combination of the four operations edge deletions, edge contractions, vertex deletions and vertex dissolutions the following containment problems are captured: testing on (induced) minors, (induced) topological minors, (induced) subgraphs, induced spanning subgraphs, dissolutions and contractions. Algorithms for detecting specific induced subgraphs such as paths and cycles have been proven to be useful in the design of algorithms that solve more general graph containment problems. We will discuss one open problem in this area and give a potential application afterwards. We first state some terminology required. Two (not necessarily induced) paths P and Q in a graph G are called mutually induced if the following two conditions are both satisfied: (i) P and Q are vertex-disjoint; (ii) G has no edges with one end-vertex in P and the other one in Q.
|Item Type:||Monograph (Working Paper)|
|Full text:||(AO) Author's Original|
Download PDF (144Kb)
|Publisher Web site:||UNSPECIFIED|
|Date accepted:||No date available|
|Date deposited:||No date available|
|Date of first online publication:||2011|
|Date first made open access:||No date available|
Save or Share this output
|Look up in GoogleScholar|