Abstract. A signed graph [Formula: see text] is a graph [Formula: see text] where each edge is assigned a positive or negative sign according to a function [Formula: see text]. We study chip-firing on such objects, employing a general theory of chip-firing on invertible matrices introduced by Guzmán and Klivans. Here a negative edge designates an adversarial relationship, so that firing a vertex incident to such an edge leads to a loss of chips at both endpoints. The chip-firing rule for [Formula: see text] is described by its reduced Laplacian matrix [Formula: see text], which also defines the critical group [Formula: see text]. The valid chip configurations are given by the lattice points of a rational cone determined by [Formula: see text] and the underlying graph [Formula: see text]. This gives rise to notions of critical as well as [Formula: see text]- superstable configurations, both of which are counted by the determinant of [Formula: see text]. We establish general results regarding these configurations, focusing on efficient methods of verifying the underlying properties. We then study the critical groups of signed graphs in the context of vertex switching and Smith normal forms. We use this to compute the critical groups of various classes of signed graphs including signed cycles, complete graphs, and wheels, in the process generalizing results of Biggs and others.

We say that a pure $d$-dimensional simplicial complex $\Delta$ on $n$ vertices is shelling completable if $\Delta$ can be realized as the initial sequence of some shelling of $\Delta_{n-1}^{(d)}$, the $d$-skeleton of the $(n-1)$-dimensional simplex. A well-known conjecture of Simon posits that any shellable complex is shelling completable. In this note we prove that vertex decomposable complexes are shelling completable. In fact we show that if $\Delta$ is a vertex decomposable complex, then there exists an ordering of its ground set $V$ such that adding the revlex smallest missing $(d+1)$-subset of $V$ results in a complex that is again vertex decomposable. We explore applications to matroids and shifted complexes, as well as connections to ridge-chordal complexes and $k$-decomposability. We also show that if $\Delta$ is a $d$-dimensional complex on at most $d+3$ vertices, then the notions of shellable, vertex decomposable, shelling completable, and extendably shellable are all equivalent.

Opportunistic Mobile Social Networks (OMSNs), formed by people moving around carrying mobile devices such as smartphones, PDAs, and laptops, have become popular in recent years. The OMSNs we discuss here are a special kind of delay tolerant networks (DTNs) that help enhance spontaneous interaction and communication among users that opportunistically encounter each other, without additional infrastructure support. Multicast is an important routing service in OMSNs which supports the dissemination of messages to a group of users. Most of the existing multicast algorithms are designed for general-purpose DTNs where social factors are neglected or reflected in static social features which are not updated to catch nodes' dynamic contact behavior. In this paper, we introduce the concept of dynamic social features and its enhancement to capture nodes' dynamic contact behavior, consider more social relationships among nodes, and adopt the community structure in the multicast compare-split scheme to select the best relay node for each destination in each hop to improve multicast efficiency. We propose two multicast algorithms based on these new features. The first community and social feature-based multicast algorithm is called Multi-CSDO which involves destination nodes only in community detection, and the second one is called Multi-CSDR which involves both the destination nodes and the relay candidates in community detection. The analysis of the algorithms is given and simulation results using a real trace of an OMSN show that our new algorithms outperform the existing one in terms of delivery rate, latency, and number of forwardings.

A rainbow graph is a graph that admits a vertex-coloring such that every color appears exactly once in the neighborhood of each vertex. We investigate some properties of rainbow graphs. In particular, we show that there is a bijection between the isomorphism classes of $n$-rainbow graphs on $2n$ vertices and the switching classes of graphs on $n$ vertices.