Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 6 of 6 for “"end vertex"”.
-
On End Vertices of Search Algorithms
Given a graph G=(V,E), a vertex ordering of G is a total order v1,v2,...,vn of V. A graph search algorithm is a systematic method for visiting each vertex in a graph, naturally producing a vertex ordering of the graph. We explore the problem of determining whether a given vertex in a graph can be …
-
Related Orderings of AT-Free Graphs
… We also consider a problem of another type: S-End-Vertex, where S is one of the following search algorithms: breadth-first search (BFS), lexicographic breadth-first search (LBFS), depth-first search (DFS), and maximal neighbourhood search (MNS). This problem asks if a specified vertex can be …
-
Deducing Vertex Weights From Empirical Occupation Times
… the study of human problem solving: Let $G$ be a vertex-weighted digraph with marked "start" and "end" vertices. Suppose that a random walker begins at the start vertex, steps to neighbors of vertices with probability proportional to their weights, and stops upon reaching the end vertex. Could one …
-
Hamiltonian line graphs and claw -free graphs
… where Z8 is obtained by identifying one end-vertex of P9 with one vertex of a triangle; let hc( G) denote the least integer m such that the iterated line graph Lm(G) is Hamilton-connected, we showed that k -- 1 ≤ hc( G) ≤ max{lcub}diam(G), k -- 1{rcub}, where k is the length of a longest …
-
Proper connection number of graphs
… Andrews et al.\cite{Andrews2016} and, independently, Borozan et al.\cite{Borozan2012} introduced the concept of proper connection number as follows: A coloured path $P$ in an edge-coloured graph $G$ is called a \emph{properly coloured path} or more simple \emph{proper path} if two any …
-
Circuits and Cycles in Graphs and Matroids
… P is a bridge divalent path of G; if the two ends of P are of degree s and t, respectively, then P is called a divalent (s, t)-path. Let l(G) = max{m : G has a divalent path of length m that is not both of length 2 and in a K3}. We prove the following. (i) If G is a connected triangular graph, …