Invariante kemijske teorije grafov na hipergrafih : doktorska disertacija

Romih, Gašper Domen (author), Klavžar, Sandi (mentor)

Kemijska teorija grafov obravnava modeliranje kemijskih struktur z grafi. Za ta namen je bilo definiranih veliko različnih invariant na grafih. Ena izmed najbolj znanih invariant je Wienerjev indeks. V nekaterih primerih je mogoče graf izometrično vložiti v $\ell_1$-prostor, pri čemer imajo taki grafi koristne lastnosti za izračun različnih indeksov. Skozi leta je uporaba $\ell_1$-vložitev, za izračun različnih grafovskih invariant, dobila ime prerezna metoda. V disertaciji obravnavamo sorodne problem na hipergrafih. V zadnjem času se pojavlja vse več raziskav, ki obravnavajo izračun Wienerjevega indeksa na hipergrafih. V delu tako opišemo prerezno metodo, ki jo posplošimo na hipergrafe, njeno uporabo pa prikažemo predvsem za izračun Wienerjevega indeksa hipergrafa. Pri tem uvedemo pojma hipergraf kocke in hipergraf delne kocke ter predstavimo posplošitve znanih izrekov iz teorije grafov na hipergrafe. Med te posplošitve sodita karakterizacija hipergraf delnih kock in kanonična metrična vložitev hipergrafov. Nadalje se posvetimo različnim operacijam na hipergrafih, ki hipergrafu dodajo nova vozlišča ali povezave, pri čemer analiziramo $\ell_1$-vložljivost dobljenih hipergrafov. Prav tako se posvetimo tudi izračunu Wienerjevega indeksa dobljenega hipergrafa ter, ko je to mogoče, izpeljemo zvezo med Wienerjevim indeksom začetnega in končnega hipergrafa. Pokažemo tudi, da lahko s pomočjo teh operacij konstruiramo hipergrafe, ki so motivirani iz kemijske teorije grafov. V posebnem delu se osredotočimo na nekatere konkretne družine hipergrafov, kot so sončnice, tesne hiperpoti in tesni hipercikli. Dodatno obravnavamo tudi nekaj posebnih kemijsko motiviranih družin hipergrafov kot so hipergraf fenileni, Clarovi hipergrafi ter hipergraf zaprte soseščine. Za konec podamo definicije nekaterih drugih indeksov na hipergrafih ter pokažemo, da razvite metode v svoji osnovni obliki delujejo tudi v teh primerih. Ugotovili smo, da poleg Wienerjeva indeksa, drugi indeksi v literaturi v kontekstu hipergrafov še niso definirani ter obravnavani. V delu definiramo Segedski ter $PI$ indeks na hipergrafih, poleg tega pa formuliramo tudi osnovno obliko prerezne metode za izračun le teh.

• Language: Slovenian
• Keywords: Wienerjev indeks, hipergraf, hipergraf delna kocka vložitve, l1-prostor, l1-vložitev
• Work type: Doctoral dissertation
• Typology: 2.08 - Doctoral Dissertation
• Organization: FMF - Faculty of Mathematics and Physics
• Year: 2025
• PID: 20.500.12556/RUL-174319
• UDC: 519.17
• COBISS.SI-ID: 250646019
• Publication date in RUL: 01.10.2025

Secondary language

• Language: English
• Title: Invariants of chemical graph theory on hypergraphs

Abstract

Chemical graph theory studies the modeling of chemical structures by graphs. For this purpose, many different graph invariants have been defined. One of the most well-known invariants is the Wiener index. In certain cases, a graph can be isometrically embedded into the $\ell_1$-space, which provides useful properties for the computation of various indices. Over the years, the use of $\ell_1$-embeddings for this purpose has become known as the cut method. In this dissertation, we address related problems in the context of hypergraphs. Recently, an increasing number of studies have focused on the computation of the Wiener index for hypergraphs. In this work, we extend the cut method to hypergraphs and demonstrate its application, primarily for the calculation of the Wiener index. To this end, we introduce the notions of cube hypergraphs and partial cube hypercubes, and present generalizations of classical theorems from graph theory to the hypergraph setting. These generalizations include a characterization of partial cube hypercubes and the canonical metric embedding of hypergraphs. We further study various operations on hypergraphs that generate new structures by adding vertices or hyperedges, and analyze the $\ell_1$-embeddability of the resulting hypergraphs. Moreover, we investigate the Wiener index of these new hypergraphs and, whenever possible, establish relations between the indices of the original and the resulting hypergraphs. We also show that such operations allow for the construction of hypergraphs naturally motivated by chemical graph theory. Special attention is devoted to several concrete families of hypergraphs, such as sunflowers, tight hyperpaths, and tight hypercycles. In addition, we examine chemically motivated families of hypergraphs, including phenylene hypergraphs, Clar hypergraphs, and closed neighborhood hypergraphs. Finally, we introduce definitions of other indices for hypergraphs and demonstrate that the developed methods can be adapted to these cases as well. We find that, apart from the Wiener index, other indices have not yet been formally defined or studied in the context of hypergraphs. To this end, we define the Szeged and $PI$ indices for hypergraphs and formulate a basic version of the cut method for their computation.

• Keywords: Wiener index, hypergraph, hypergraph partial cube, l1-space, l1-embedding