Extremal Problems On The Hitting Time And Related Invariants Of Graphs

Random walk on graph is one of the hot topics in graph theory research,and it has important application in computer science,information science,electrical network and other branches.Hitting time is one of the important problems of random walk on the graph,hitting time and its related invariants have been widely studied by scholars.The relationship between electrical network and random walk on graph is expounded in Doyle’s monograph.Klein et al.proposed the concept of effective resistance and established the relationship between effective resistance and random walk.Starting from the structure of the graph,some scholars have studied the extremum of the hitting time and its related invariants of trees and unicyclic graphs.In this thesis,we mainly study the extremal problem of hitting time and its related invariants in bicyclic graphs.The following is the main structure and research content of this thesis.In the first chapter,the basic concepts and terms of graph theory involved in this thesis are introduced.The research background and current situation of hitting time and its related invariants are described in detail,and the main results of this thesis are briefly described.In the second chapter,we mainly study the extremal problem of RC(x)(reverse cover cost)in a class of bicyclic graphs.By using effective resistance and Kirchhoff index and other parameters,we characterize the corresponding extremal graph and the position of vertex x in the graph when RC(x)reaches the extremum.In the third chapter,we mainly study the extremal problem of CC(x)(cover cost)in a class of bicyclic graphs.By using effective resistance and Kirchhoff index and other parameters,we characterize the corresponding extremal graph and the position of vertex x in the graph when CC(x)reaches the extremum.In the fourth chapter,we mainly study the extremal problem of φ(G)(the maximum value of hitting time between two vertices in graph G)in a class of bicyclic graph.By using effective resistance,we characterize the corresponding extremal graph and the position of two vertices in the graph when φ(G)reaches the extremum.In the fifth chapter,we mainly study the extremal problem of Kirchhoff index in a class of bicyclic graphs.We characterize the corresponding extremal graph when additive degree Kirchhoff index(multiplicative degree Kirchhoff index)reaches the extremum.