A graph G is a star-k-PCG if there exists a non-negative edge weighted star tree S and k mutually exclusiveintervals I_1,I_2,...,I_k of non-negative reals such that each vertex of -g corresponds to a leaf of S and there is an edge between two vertices in G if the distance between their corresponding leaves in S lies in the union of these intervals. 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.
On Graphs that are not Star-K-PCGs (short paper) / Monti, A.; Sinaimeri, B.. - 3587:(2023), pp. 92-97. (Intervento presentato al convegno The 24th Italian Conference on Theoretical Computer Science, ICTCS2023 tenutosi a Palermo, Italy).
On Graphs that are not Star-K-PCGs (short paper)
Monti A.Co-primo
;Sinaimeri B.Co-primo
2023
Abstract
A graph G is a star-k-PCG if there exists a non-negative edge weighted star tree S and k mutually exclusiveintervals I_1,I_2,...,I_k of non-negative reals such that each vertex of -g corresponds to a leaf of S and there is an edge between two vertices in G if the distance between their corresponding leaves in S lies in the union of these intervals. 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
