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 S and there is an edge between two vertices in G if the distance between their corresponding leaves in S lies in I1 U I2 U … U Ik. These graphs are related to different well-studied classes of graphs such as PCGs and multithreshold graphs. It is well known that for any graph G there exists a k such that G is a star-k-PCG. Thus, for a given graph G it is interesting to know which is the minimum k such that G is a star-k-PCG. In this paper, we focus on classes of graphs where k is constant and prove that circular graphs and two dimensional grid graphs are both star-2-PCGs and that they are not star-1-PCGs. Moreover we show that 4-dimensional grids are not star-2-PCG.
On Star-Multi-interval Pairwise Compatibility Graphs / Monti, Angelo; Sinaimeri, Blerina. - 13973:(2023), pp. 267-278. (Intervento presentato al convegno International Conference and Workshops on Algorithms and Computation: WALCOM: Algorithms and Computation. WALCOM 2023 tenutosi a Taiwan) [10.1007/978-3-031-27051-2_23].
On Star-Multi-interval Pairwise Compatibility Graphs
Angelo MontiPrimo
;Blerina Sinaimeri
Secondo
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 S and there is an edge between two vertices in G if the distance between their corresponding leaves in S lies in I1 U I2 U … U Ik. These graphs are related to different well-studied classes of graphs such as PCGs and multithreshold graphs. It is well known that for any graph G there exists a k such that G is a star-k-PCG. Thus, for a given graph G it is interesting to know which is the minimum k such that G is a star-k-PCG. In this paper, we focus on classes of graphs where k is constant and prove that circular graphs and two dimensional grid graphs are both star-2-PCGs and that they are not star-1-PCGs. Moreover we show that 4-dimensional grids are not star-2-PCG.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
