2019/06/08 by Li Dai, Dai, Li, Dianlong Yu +3 · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #Distributed Control Multi-Agent Systems #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Search Problems #cs.DM #math.CO #math.OC
paper · pdf · doi:10.48550/arxiv.1906.03384
arxiv created 2019/06/08 · openalex publication_date 2019/06/08 · openalex created_date 2019/06/14 · arxiv updated 2022/02/08 · openalex updated_date 2026/07/28
The problem of leaders location plays an important role in the controllability of undirected graphs.The concept of minimal perfect critical vertex set is introduced by drawing support from the eigenvector of Laplace matrix. Using the notion of minimal perfect critical vertex set, the problem of finding the minimum number of controllable leader vertices is transformed into the problem of finding all minimal perfect critical vertex sets. Some necessary and sufficient conditions for special minimal perfect critical vertex sets are provided, such as minimal perfect critical 2 vertex set, and minimal perfect critical vertex set of path or path related graphs. And further, the leaders location problem for path graphs is solved completely by the algorithm provided in this paper. An interesting result that there never exist a minimal perfect critical 3 vertex set is proved, too.