A graph G is a star-K-PCG if there exists a non-negative edge weighted star tree S and K mutually exclusive intervals I1, I2, . . . , IK of non-negative reals such that each vertex of G corresponds to a leaf of G and there is an edge between two vertices in G if the distance between their corresponding leaves in G lies in I1 u2 . . . UK. These graphs are related to different well-studied classes of graphs such as PCGs and multithreshold graphs. In this paper, we investigate the smallest value of N such that there exists an n vertex graph that is not a star-K-PCG, for small values of K.
Monti, A.; Sinaimeri, Blerina. (2023). On Graphs that are not Star-K-PCGs (short paper). In CEUR Workshop Proceedings (pp. 92- 97).
On Graphs that are not Star-K-PCGs (short paper)
Sinaimeri B.
2023
Abstract
A graph G is a star-K-PCG if there exists a non-negative edge weighted star tree S and K mutually exclusive intervals I1, I2, . . . , IK of non-negative reals such that each vertex of G corresponds to a leaf of G and there is an edge between two vertices in G if the distance between their corresponding leaves in G lies in I1 u2 . . . UK. These graphs are related to different well-studied classes of graphs such as PCGs and multithreshold graphs. In this paper, we investigate the smallest value of N such that there exists an n vertex graph that is not a star-K-PCG, for small values of K.
| File | Dimensione | Formato | |
|---|---|---|---|
|
0910.pdf
Open Access
Tipologia:
Versione dell'editore
Licenza:
Creative commons
Dimensione
1.4 MB
Formato
Adobe PDF
|
1.4 MB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
