Laplacian controllability analysis of chain graph based on minimal perfect critical vertex set

Li Dai; Li Dai

doi:10.3934/math.2026319

AIMS Mathematics

2026, Volume 11, Issue 3: 7766-7778. doi: 10.3934/math.2026319

Previous Article Next Article

Research article Topical Sections

Laplacian controllability analysis of chain graph based on minimal perfect critical vertex set

Li Dai ^,

College of Science, National University of Defense Technology, Changsha 410073, Hunan, China

Received: 23 November 2025 Revised: 02 March 2026 Accepted: 05 March 2026 Published: 24 March 2026
MSC : 05C50, 15A18, 93A16

The aim is to find all of the minimum leader set for chain graphs. By analyzing the subgraph structure rather than the eigenvectors, minimal perfect critical vertex sets (MPCS) of chain graph are found. It is proved that there is one and only one MPCS in chain graph (CG) (1, 1, ⋯, 1; 1, 1, ⋯, 1), and it is a 4-MPCS. Based on this, all the minimum leader sets of the chain graph are given.
- minimal perfect critical vertex set,
- chain graph,
- Laplacian controllability,
- minimum leader set,
- subgraph structure
Citation: Li Dai. Laplacian controllability analysis of chain graph based on minimal perfect critical vertex set[J]. AIMS Mathematics, 2026, 11(3): 7766-7778. doi: 10.3934/math.2026319

Related Papers:

Abstract

The aim is to find all of the minimum leader set for chain graphs. By analyzing the subgraph structure rather than the eigenvectors, minimal perfect critical vertex sets (MPCS) of chain graph are found. It is proved that there is one and only one MPCS in chain graph (CG) (1, 1, ⋯, 1; 1, 1, ⋯, 1), and it is a 4-MPCS. Based on this, all the minimum leader sets of the chain graph are given.

References

[1]	H. G. Tanner, On the controllability of nearest neighbor interconnections, 2004 43rd IEEE Conference on Decision and Control (CDC) (IEEE Cat. No. 04CH37601), Nassau, Bahamas, 2004, 2467–2472. https://doi.org/10.1109/cdc.2004.1428782
[2]	M. Ji, M. Egerstedt, A graph-theoretic characterization of controllability for multi-agent systems, 2007 American Control Conference, New York, NY, USA, 2007, 4588–4593. https://doi.org/10.1109/acc.2007.4283010
[3]	Z. J. Ji, H. S. Yu, A new perspective to graphical characterization of multiagent controllability, IEEE T. Cybernetics, 47 (2017), 1471–1483. https://doi.org/10.1109/TCYB.2016.2549034 doi: 10.1109/TCYB.2016.2549034
[4]	L. Dai, Minimum leader selection for controllability of undirected graphs with leader-follower framework, IET Control Theory A., 17 (2023), 505–515. https://doi.org/10.1049/cth2.12385 doi: 10.1049/cth2.12385
[5]	F. K. Bell, D. Cvetkovic, P. Rowlinson, S. K. Simic, Graphs for which the least eigenvalue is minimal Ⅱ, Linear Algebra Appl., 429 (2008), 2168–2179. https://doi.org/10.1016/j.laa.2008.06.018 doi: 10.1016/j.laa.2008.06.018
[6]	S.-P. Hsu, Minimal Laplacian controllability problems of threshold graphs, IET Control Theory A., 13 (2019), 1639–1645. https://doi.org/10.1049/iet-cta.2018.5875 doi: 10.1049/iet-cta.2018.5875
[7]	A. Alazemi, M. Andelic, T. Koledin, Z. Stanić, Chain graphs with simple Laplacian eigenvalues and their Laplacian dynamics, Comp. Appl. Math., 42 (2023), 6. https://doi.org/10.1007/s40314-022-02141-5 doi: 10.1007/s40314-022-02141-5
[8]	B. Alshamary, M. Andekic, E. Dolicanin, Z. Stanić, Controllable multi-agent systems modeled by graphs with exactly one repeated degree, AIMS Mathematics, 9 (2024), 25689–25704. https://doi.org/10.3934/math.20241255 doi: 10.3934/math.20241255
[9]	A. Bondy, U. S. R. Murty, Graph theory, London: Springer, 2008.
[10]	Z. J. Ji, H. S. Yu, A new perspective to graphical characterization of multiagent controllability, IEEE T. Cybernetics, 47 (2017), 1471–1483. https://doi.org/10.1109/TCYB.2016.2549034 doi: 10.1109/TCYB.2016.2549034
[11]	L. Dai, Leaders' selection for UAV swarm with two-way communication, CAAI Transactions on Intelligent Systems, 16 (2021), 484–492. https://doi.org/10.11992/tis.202006010 doi: 10.11992/tis.202006010
[12]	M. Knor, J. Sedlar, R. Škrekovski, Y. Yang, The subpath number of cactus graphs, Comp. Appl. Math., 45 (2026), 102. https://doi.org/10.1007/s40314-025-03545-9 doi: 10.1007/s40314-025-03545-9

Reader Comments

Your name:*

Email:*
© 2026 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)