We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

On finding paths passing through specified vertices.

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
Status:Not peer-reviewed
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