Abstract
In this thesis, we focus on the class of complete $S$-partite graphs, for $S$ an undirected graph possibly with self-loops, and address the problem of finding largest $2$-regular subgraphs of these graphs, which can be formulated as an integer linear program. Roughly speaking, a complete $S$-partite graph is obtained by replacing every single node of $S$ with a number of nodes, preserving the edge/non-edge relations of $S$. Our motivation in studying largest $2$-regular subgraphs is rooted in the structural systems theory, particularly in the problem of finding largest subnetworks that can sustain controllability or asymptotic stability of the corresponding subsystems. A main contribution of the thesis is to show that the integer linear program can be solved efficiently in $O(|V(S)|^3)$, independent of the order/size of the $S$-partite graph itself. Furthermore, we demonstrate through simulations that with high probability, a random $S$-partite graph contains a largest $2$-regular subgraph of the same order as that of its complete counterpart.
Committee Chair
Xudong Chen
Committee Members
Hong Hu Netanel Raviv
Degree
Master of Science (MS)
Author's Department
Electrical & Systems Engineering
Document Type
Thesis
Date of Award
Spring 5-6-2026
Language
English (en)
Author's ORCID
https://orcid.org/0009-0000-0818-0593
Recommended Citation
Jiang, Yiyang, "Largest 2-regular Subgraphs in Complete S-partite Graphs" (2026). McKelvey School of Engineering Theses & Dissertations. 1343.
https://openscholarship.wustl.edu/eng_etds/1343
Included in
Controls and Control Theory Commons, Control Theory Commons, Discrete Mathematics and Combinatorics Commons, Operational Research Commons, Theory and Algorithms Commons