Research On Cycle Of Lexicographic Depth-First Search Ordering

The graph search algorithm is a mechanism for systematically visiting the vertices of a graph,a corresponding vertex ordering will be obtained after visiting.Combining the "+" rule with the graph search algorithm produces a corresponding reverse graph search algorithm,which requires a graph and a vertex ordering as input.The number of vertex orderings on a finite graph is finite,therefore,after performing a certain graph search algorithm enough times,a sequence of orderings {σ₁,...,σ_i,...,σ_i+k}are obtained and σ_i=(σ_i+k,which is called the cycle of a certain graph search algorithm ordering,where the maximum value of k is the size of the cycle of a certain graph search algorithm.Dusart and Habib conjectured that the size of the cycle of lexicographic breadth-first search（LBFS）is 2 for cocomparability graphs and proved it holds for interval graphs.Gao and Xu proved that the size of the cycle of lexicographic breadth-first search is 2 for （?）-free cocomparability graphs.This thesis proves that the size of the cycle of lexicographic depth-first search（LDFS）is 2 for （?）-free cocomparability graphs based on the symmetry of lexicographic breadth-first search and lexicographic depth-first search.This thesis improves the method of constructing vertex orderings by Gao and Xu,and for some special subcases,the thesis proposes a new method for constructing vertex orderings with an infinite number of vertices,which has been well applied for subcases.Interval graphs are a well-known subclass of cocomparability graphs.This thesis proves that the size of the cycle of lexicographic depth-first search（LDFS）is 2 for interval graphs by constructing a circle with four vertices using properties of lexicographic depth-search ordering on cocomparability graphs.In addition to this,the properties of orderings that satisfy the cycle of lexicographic depth-first search are studied and the thesis proves that the interval ordering is obtained after taking cocomparability ordering as input of reverse lexicographic depth-first search（LDFS⁺）.Similarly,since the unit interval graphs are a subclass graph of the interval graphs,a better property is proved on the unit interval graphs,that is,the dual ordering of origin ordering is obtained after taking interval ordering as input of reverse graph search algorithm.