A Classification of Graphs through Quadratic Embedding Constants and Clique Graph Insights
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913342970396672 |
|---|---|
| author | Baskoro, Edy Tri Obata, Nobuaki |
| author_facet | Baskoro, Edy Tri Obata, Nobuaki |
| contents | The quadratic embedding constant (QEC) of a graph $G$ is a new numeric invariant, which is defined in terms of the distance matrix and is denoted by $\mathrm{QEC}(G)$. By observing graph structure of the maximal cliques (clique graph), we show that a graph $G$ with $\mathrm{QEC}(G)<-1/2$ admits a ``cactus-like'' structure. We derive a formula for the quadratic embedding constant of a graph consisting of two maximal cliques. As an application we discuss characterization of graphs along the increasing sequence of $\mathrm{QEC}(P_d)$, where $P_d$ is the path on $d$ vertices. In particular, we determine graphs $G$ satisfying $\mathrm{QEC}(G)<\mathrm{QEC}(P_5)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_03342 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A Classification of Graphs through Quadratic Embedding Constants and Clique Graph Insights Baskoro, Edy Tri Obata, Nobuaki Combinatorics primary 05C50, secondary 05C12, 05C76 The quadratic embedding constant (QEC) of a graph $G$ is a new numeric invariant, which is defined in terms of the distance matrix and is denoted by $\mathrm{QEC}(G)$. By observing graph structure of the maximal cliques (clique graph), we show that a graph $G$ with $\mathrm{QEC}(G)<-1/2$ admits a ``cactus-like'' structure. We derive a formula for the quadratic embedding constant of a graph consisting of two maximal cliques. As an application we discuss characterization of graphs along the increasing sequence of $\mathrm{QEC}(P_d)$, where $P_d$ is the path on $d$ vertices. In particular, we determine graphs $G$ satisfying $\mathrm{QEC}(G)<\mathrm{QEC}(P_5)$. |
| title | A Classification of Graphs through Quadratic Embedding Constants and Clique Graph Insights |
| topic | Combinatorics primary 05C50, secondary 05C12, 05C76 |
| url | https://arxiv.org/abs/2311.03342 |