A packet-switching network is stable if the number of packets in the network remains
bounded at all times. A very natural question that arises in the context of stability properties
of such networks is how network structure precisely affects these properties. In this work we
embark on a systematic study of this question in the context of Adversarial Queueing Theory,
which assumes that packets are adversarially injected into the network. We consider size,
diameter, maximum vertex degree, minimum number of disjoint paths that cover all edges of …

A packet-switching network is stable if the number of packets in the network remains
bounded at all times. A very natural question that arises in the context of stability and
instability properties of such networks is how network structure precisely affects these
properties. In this work, we embark on a systematic study of this question in the context of
Adversarial Queueing Theory, which assumes that packets are adversarially injected into
the network. We consider size, diameter, maximum vertex degree, minimum number of …