Angelo Monti

Tiziana Calamoneri, Angelo Monti, Fabrizio Petroni

A graph G is a multi-interval PCG if there exist an edge weighted tree T with non-negative real values and disjoint intervals of the non-negative real half-line such that each node of G is uniquely associated to a leaf of T and there is an edge between two nodes in G if and only if the weighted distance between their corresponding leaves in T lies within any such intervals. If the number of intervals is k, then we call the graph a k-interval-PCG; in symbols, G = k-interval-PCG (T, I1, . . . , Ik). It is known that 2-interval-PCGs do not contain all graphs and the smallest known graph outside this class has 135 nodes. Here we prove that all graphs with at most 8 nodes are 2-interval-PCGs, so doing one step towards the determination of the smallest value of n such that there exists an n node graph that is not a 2-interval-PCG.

Angelo Monti, Blerina Sinaimeri

For a positive integer $s$, an $s$-club in a graph $G$ is a set of vertices inducing a subgraph with diameter at most $s$. As generalizations of cliques, $s$-clubs offer a flexible model for real-world networks. This paper addresses the problems of partitioning and disjoint covering of vertices with $s$-clubs on bipartite graphs. First we consider the $(k,s)$-PC problem where ask whether the vertices of $G$ can be partitioned into at most $k$ disjoint $s$-clubs. We prove that for any fixed $k \geq 2$ and for any fixed odd $s \geq 3$ or even $s\geq 8$, the $(k,s)$-PC problem is NP-complete even for bipartite graphs. Note that our NP-completeness result is stronger than the one in Abbas and Stewart (1999), as we assume that both $s$ and $k$ are constants and not part of the input. Additionally, we study the Maximum Disjoint $(t,s)$-Club Covering problem ($(t,s)$-MAX-DCC), which aims to find a collection of vertex-disjoint $(t,s)$-clubs (i.e. $s$-clubs with at least $t$ vertices) that covers the maximum number of vertices in $G$. We prove that it is NP-hard to achieve an approximation factor of $\frac{95}{94} $ for $(t,3)$-MAX-DCC for any fixed $t\geq 8$ and for $(t,2)$-MAX-DCC for any fixed $t\geq 5$ even for bipartite graphs. Previously, results were known only for $(3,2)$-MAX-DCC. Finally, we provide a polynomial-time algorithm for $(2,2)$-MAX-DCC resolving an open problem from Dondi \textit{et al.} (2019).