The H-property of Line Graphons

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationASCC 2022 - 2022 13th Asian Control Conference, Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages6
ISBN (Electronic)9788993215236
StatePublished - 2022
Externally publishedYes
Event13th Asian Control Conference, ASCC 2022 - Jeju, Korea, Republic of
Duration: May 4 2022May 7 2022

Publication series

NameASCC 2022 - 2022 13th Asian Control Conference, Proceedings


Conference13th Asian Control Conference, ASCC 2022
Country/TerritoryKorea, Republic of


  • Graph Theory
  • Graphons
  • Network Control

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Control and Optimization


Dive into the research topics of 'The H-property of Line Graphons'. Together they form a unique fingerprint.

Cite this