TY - GEN
T1 - The H-property of Line Graphons
AU - Belabbas, Mohamed Ali
AU - Chen, Xudong
AU - Basar, Tamer
N1 - The first two authors contributed equally to the manuscript in all categories. This work was supported by the National Science Foundation [ECCS-1809076, ECCS-2042360] and the Air Force Office of Scientific Research [FA9550-19-1-0353, FA9550-20-1-0076, FA9550-20-1-0333].
PY - 2022
Y1 - 2022
N2 - We explore in this paper sufficient conditions for the H-property to hold, with a particular focus on the so-called line graphons. A graphon is a symmetric, measurable function from the unit square to the closed unit interval. Graphons can be used to sample random graphs, and a graphon is said to have the H-property if graphs on n nodes sampled from it admit a node-cover by disjoint cycles - such a cover is called a Hamiltonian decomposition - almost surely asymptically in the size of the graph.. A step-graphon is a graphon which is piecewise constant over rectangles in the domain. To a step-graphon, we assign two objects: its concentration vector, encoding the areas of the rectangles, and its skeleton-graph, describing their supports. These two objects were used in our earlier work to establish necessary conditions for a step-graphon to have the H-property. In this paper, we prove that these conditions are essentially also sufficient for the class of line-graphons, i.e., the step-graphons whose skeleton graphs are line graphs with a self-loop at an ending node. We also investigate borderline cases where neither the necessary nor the sufficient conditions are met.
AB - We explore in this paper sufficient conditions for the H-property to hold, with a particular focus on the so-called line graphons. A graphon is a symmetric, measurable function from the unit square to the closed unit interval. Graphons can be used to sample random graphs, and a graphon is said to have the H-property if graphs on n nodes sampled from it admit a node-cover by disjoint cycles - such a cover is called a Hamiltonian decomposition - almost surely asymptically in the size of the graph.. A step-graphon is a graphon which is piecewise constant over rectangles in the domain. To a step-graphon, we assign two objects: its concentration vector, encoding the areas of the rectangles, and its skeleton-graph, describing their supports. These two objects were used in our earlier work to establish necessary conditions for a step-graphon to have the H-property. In this paper, we prove that these conditions are essentially also sufficient for the class of line-graphons, i.e., the step-graphons whose skeleton graphs are line graphs with a self-loop at an ending node. We also investigate borderline cases where neither the necessary nor the sufficient conditions are met.
KW - Graph Theory
KW - Graphons
KW - Network Control
UR - http://www.scopus.com/inward/record.url?scp=85135605085&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85135605085&partnerID=8YFLogxK
U2 - 10.23919/ASCC56756.2022.9828212
DO - 10.23919/ASCC56756.2022.9828212
M3 - Conference contribution
AN - SCOPUS:85135605085
T3 - ASCC 2022 - 2022 13th Asian Control Conference, Proceedings
SP - 953
EP - 958
BT - ASCC 2022 - 2022 13th Asian Control Conference, Proceedings
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 13th Asian Control Conference, ASCC 2022
Y2 - 4 May 2022 through 7 May 2022
ER -