Abstract A graph $$G=(V,E)$$ G = ( V , E ) is a star-k-pairwise compatibility graph (star-k-PCG) if there exists a weight function $$w: V \rightarrow \mathbb {R}^+$$ w : V → R + and k mutually exclusive intervals $$I_1, I_2, \ldots I_k$$ I 1 , I 2 , … I k , such that there is an edge $$uv \in E$$ u v ∈ E if and only if $$w(u)+w(v) \in \bigcup _i I_i$$ w ( u ) + w ( v ) ∈ ⋃ i I i . These graphs are related to two important classes of graphs: pairwise compatibility graphs (PCGs) and multithreshold graphs. It is 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. We define this minimum k as the star number of the graph, denoted by $$\gamma (G)$$ γ ( G ) . Here we investigate the star number of simple graph classes, such as graphs of small size, caterpillars, cycles and grids. Specifically, we determine the exact value of $$\gamma (G)$$ γ ( G ) for all the graphs with at most 7 vertices. By doing so we show that the smallest graphs with star number 2 are only 4 and have exactly 5 vertices; the smallest graphs with star number 3 are only 3 and have exactly 7 vertices. Next, we provide a construction showing that the star number of caterpillars is one. Moreover, we show that the star number of cycles and two-dimensional grid graphs is 2 and that the star number of 4-dimensional grids is at least 3. Finally, we conclude with numerous open problems.

Abstract A graph $G=(V,E)$ is defined as a star-$k$-pairwise compatibility graph (PCG) when it is possible to assign a positive real number weight $w$ to each vertex $V$, and define $k$ distinct intervals $I_{1}, I_{2}, \ldots I_{k}$, in such a way that there is an edge $uv$ in $E$ if and only if the sum of the weights of vertices $u$ and $v$ falls within the union of these intervals. The star-$k$-PCG class is connected to two significant graph categories: PCGs and multithreshold graphs. The star number of a graph $G$, is the smallest $k$ for which $G$ is a star-$k$-PCG. In this paper, we study the effects of various graph operations, such as the addition of twins, pendant vertices, universal vertices, or isolated vertices, on the star number of the graph resulting from these operations. As significant applications of our findings, we determine the star number of lobster graphs and provide an upper bound for the star number of acyclic graphs. This is particularly interesting as determining the star number is notoriously difficult and is known only for a few classes of graphs. Indeed, for acyclic graphs, the exact value of the star number is currently known only for caterpillars [1].

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 , I 1 ,…, I k ). 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.

Abstract We study deterministic fault‐tolerant gossiping protocols in geometric radio networks. Node and link faults may happen during every time‐slot of the protocol's execution. We first consider the model where every node can send at most one message per time‐slot. We provide a protocol that completes gossiping inO(nΔ) time (wherenis the number of nodes and Δ is the maximal in‐degree) and has message complexityO(n2). Both bounds are then shown to be optimal. Second, we consider the model where messages can be arbitrarily combined and sent in one time‐slot. We give a protocol working in optimal completion timeO(DΔ) (whereDis the maximal source eccentricity) and message complexityO(Dn). © 2012 Wiley Periodicals, Inc. NETWORKS, Vol. 2012

Markovian evolving graphs are dynamic-graph models where the links among a fixed set of nodes change during time according to an arbitrary Markovian rule. They are extremely general and they can well describe important dynamic-network scenarios. We study the speed of information spreading in the stationary phase by analyzing the completion time of the flooding mechanism. We prove a general theorem that establishes an upper bound on flooding time in any stationary Markovian evolving graph in terms of its node-expansion properties. We apply our theorem in two natural and relevant cases of such dynamic graphs. Geometric Markovian evolving graphs where the Markovian behaviour is yielded by n mobile radio stations, with fixed transmission radius, that perform independent random walks over a square region of the plane. Edge-Markovian evolving graphs where the probability of existence of any edge at time t depends on the existence (or not) of the same edge at time t-1. In both cases, the obtained upper bounds hold with high probability and they are nearly tight. In fact, they turn out to be tight for a large range of the values of the input parameters. As for geometric Markovian evolving graphs, our result represents the first analytical upper bound for flooding time on a class of concrete mobile networks.

We consider a Mobile Ad-hoc NETwork (MANET) formed by n agents that move at speed V according to the Manhattan Random-Way Point model over a square region of side length L. The resulting stationary (agent) spatial probability distribution is far to be uniform: the average density over the "central zone" is asymptotically higher than that over the "suburb". Agents exchange data iff they are at distance at most R within each other.

=1We introduce stochastic time-dependency in evolving graphs: starting from an initial graph, at every time step, every edge changes its state (existing or not) according to a two-state Markovian process with probabilities p (edge birth-rate) and q (edge death-rate). If an edge exists at time t, then, at time $t+1$, it dies with probability q. If instead the edge does not exist at time t, then it will come into existence at time $t+1$ with probability p. Such an evolving graph model is a wide generalization of time-independent dynamic random graphs [A. E. F. Clementi, A. Monti, F. Pasquale, and R. Silvestri, J. Comput. System Sci., 75 (2009), pp. 213–220] and will be called edge-Markovian evolving graphs. We investigate the speed of information spreading in such evolving graphs. We provide nearly tight bounds (which in fact turn out to be tight for a wide range of probabilities p and q) on the completion time of the flooding mechanism aiming to broadcast a piece of information from a source node to all nodes. In particular, we provide i) a tight characterization of the class of edge-Markovian evolving graphs where flooding time is constant and, thus, it does not asymptotically depend on the initial graph; ii) a tight characterization of the class of edge-Markovian evolving graphs where flooding time does not asymptotically depend on the edge death-rate q. An interesting consequence of our results is that information spreading can be fast even if the graph, at every time step, is very sparse and disconnected. Furthermore, our bounds imply that the flooding time can be exponentially shorter than the mixing time of the edge-Markovian graph.

A set $\mathcal{F}$ of ordered k-tuples of distinct elements of an n-set is pairwise reverse free if it does not contain two ordered k-tuples with the same pair of elements in the same pair of coordinates in reverse order. Let $F(n,k)$ be the maximum size of a pairwise reverse-free set. In this paper we focus on the case of 3-tuples and prove $\lim F(n,3)/\binom{n}{3}=5/4$, more exactly, $\frac{5}{24}n^3-\frac{1}{2}n^2-O(n\log n)

Markovian evolving graphs are dynamic-graph models where the links among a fixed set of nodes change during time according to an arbitrary Markovian rule. They are extremely general and they can well describe important dynamic-network scenarios. We study the speed of information spreading in the stationary phase by analyzing the completion time of the flooding mechanism. We prove a general theorem that establishes an upper bound on flooding time in any stationary Markovian evolving graph in terms of its node-expansion properties. We apply our theorem in two natural and relevant cases of such dynamic graphs: edge-Markovian evolving graphs where the probability of existence of any edge at time t depends on the existence (or not) of the same edge at time t-1; geometric Markovian evolving graphs where the Markovian behaviour is yielded by n mobile radio stations, with fixed transmission radius, that perform n independent random walks over a square region of the plane. In both cases, the obtained upper bounds are shown to be nearly tight and, in fact, they turn out to be tight for a large range of the values of the input parameters.

The Min Energy Broadcast problem consists in assigning transmission ranges to the nodes of an ad-hoc network in order to guarantee a directed spanning tree from a given source node and, at the same time, to minimize the energy consumption (i.e. the energy cost) yielded by the range assignment. Min Energy Broadcast is known to be NP-hard. We consider random-grid networks where nodes are chosen independently at random from the n points of a √n x √n square grid in the plane. The probability of the existence of a node at a given point of the grid does depend on that point, that is, the probability distribution can be non-uniform.

We introduce stochastic time-dependency in evolving graphs: starting from an arbitrary initial edge probability distribution, at every time step, every edge changes its state (existing or not) according to a two-state Markovian process with probabilities p (edge birth-rate) and q (edge death-rate). If an edge exists at time t then, at time t+1, it dies with probability q. If instead the edge does not exist at time t, then it will come into existence at time t+1 with probability p.

We study the completion time of distributed broadcast protocols in dynamic radio networks. The dynamic network is modelled by means of adversaries: we consider two of them that somewhat are the extremal cases.

Summary form only given. We introduce the weighted version of the range assignment problem in which the cost a station s pays to transmit to another station depends on the distance between the stations and on the energy cost of station s. Most of the algorithm results for the unweighted range assignment problem can not be applied to the weighted version. We thus provide a set of algorithmic results for this version and discuss some interesting related open questions.

One of the most frequent tasks in multi-hop synchronous radio networks is the multi-broadcast operation: it consists in performing r independent message broadcasts through a network of n nodes. We investigate the case in which messages have logarithmic bounded size and the nodes have no knowledge of the topology (i.e. unknown networks).

The Nesetril--Pultr dimension of the Kneser graph is interpreted as the shortest length of strings over an infinite alphabet representing the vertices of the graph so that the absence of coincidences in the codewords of a pair of vertices is equivalent to adjacency, i.e., to the two underlying sets being disjoint. We study analogous but more demanding representations in case the alphabet size may be limited and yet the full intersection has to be determined from the coincidences. Our results introduce a connectionbetween extremal set theory and zero-error problems in multiterminal source coding in the Shannon sense.

We prove that no nonregular deterministic context-free language is accepted by any systolic Y-tree automaton while some of them, but not all, can be accepted by nondeterministic systolic Y-tree automata. We show that weak superstable systolic automata over incomplete Y-tree can accept only regular languages. We also show that the weak superstability and the superstability problems are decidable for deterministic systolic automata over a sparse and superprefix Y-tree. Moreover we prove that the regularity problem is decidable for systolic binary tree automata.