On the maximum size of connected hypergraphs without a path of given length

In this note we asymptotically determine the maximum number of hyperedges possible in an $r$-uniform, connected $n$-vertex hypergraph without a Berge path of length $k$, as $n$ and $k$ tend to infinity. We show that, unlike in the graph case, the multiplicative constant is smaller with the assumption of connectivity.     

On Eulerian orientations of even-degree hypercubes

It is well known that every Eulerian orientation of an Eulerian $2k$-edge connected (undirected) graph is strongly $k$-edge connected. A long-standing goal in the area is to obtain analogous results for other types of connectivity, such as node connectivity. We show that every Eulerian orientation of the hypercube of degree $2k$ is strongly $k$-node connected.     

The relationship between k-forcing and k-power domination

Zero forcing and power domination are iterative processes on graphs where an initial set of vertices are observed, and additional vertices become observed based on some rules. In both cases, the goal is to eventually observe the entire graph using the fewest number of initial vertices. The concept of $k$-power domination was introduced by Chang et al. (2012) as a generalization of power domination and standard graph domination. Independently, $k$-forcing was defined by Amos et al. (2015) to generalize zero forcing. In this paper, we combine the study of $k$-forcing and $k$-power domination, providing a new approach to analyze both processes. We give a relationship between the $k$-forcing and the $k$-power domination numbers of a graph that bounds one in terms of the other. We also obtain results using the contraction of subgraphs that allow the parallel computation of $k$-forcing and $k$-power dominating sets.     

Every signed planar graph without cycles of length from 4 to 8 is 3-colorable

In this paper, we investigate the signed graph version of Erdös problem: Is there a constant $c$ such that every signed planar graph without $k$-cycles, where $4\le k\le c$, is 3-colorable and prove that each signed planar graph without cycles of length from 4 to 8 is 3-colorable.     

A branch-and-price-and-cut method for computing an optimal bramble

Given an undirected graph, a bramble is a set of connected subgraphs (called bramble elements) such that every pair of subgraphs either contains a common node, or such that an edge $(i,j)$ exists with node $i$ belonging to one subgraph and node $j$ belonging to the other. In this paper we examine the problem of finding the bramble number of a graph, along with a set of bramble elements that yields this number. The bramble number is the largest cardinality of a minimum hitting set over all bramble elements on this graph. A graph with bramble number $k$ has a treewidth of $k-1$. We provide a branch-and-price-and-cut method that generates columns corresponding to bramble elements, and rows corresponding to hitting sets. We then examine the computational efficacy of our algorithm on a randomly generated data set.     

Random sampling of bandlimited signals on graphs

We study the problem of sampling k-bandlimited signals on graphs. We propose two sampling strategies that consist in selecting a small subset of nodes at random. The first strategy is non-adaptive, i.e., independent of the graph structure, and its performance depends on a parameter called the graph coherence. On the contrary, the second strategy is adaptive but yields optimal results. Indeed, no more than $O(k\log ?(k))$ measurements are sufficient to ensure an accurate and stable recovery of all k-bandlimited signals. This second strategy is based on a careful choice of the sampling distribution, which can be estimated quickly. Then, we propose a computationally efficient decoder to reconstruct k-bandlimited signals from their samples. We prove that it yields accurate reconstructions and that it is also stable to noise. Finally, we conduct several experiments to test these techniques.     

Online maximum k-coverage

We study an online model for the maximum $k$-vertex-coverage problem, in which, given a graph $G=(V,E)$ and an integer $k$, we seek a subset $A?V$ such that $\left|A\right|=k$ and the number of edges covered by $A$ is maximized. In our model, at each step $i$, a new vertex $v_i$ is released, and we have to decide whether we will keep it or discard it. At any time of the process, only $k$ vertices can be kept in memory; if at some point the current solution already contains $k$ vertices, any inclusion of a new vertex in the solution must entail the definite deletion of another vertex of the current solution (a vertex not kept when released is definitely deleted). We propose algorithms for several natural classes of graphs (mainly regular and bipartite), improving on an easy $\frac{1}{2}$-competitive ratio. We next settle a set version of the problem, called the maximum $k$-(set)-coverage problem. For this problem, we present an algorithm that improves upon former results for the same model for small and moderate values of $k$.     

Monochromatic tree covers and Ramsey numbers for set-coloured graphs

We consider a generalisation of the classical Ramsey theory setting to a setting where each of the edges of the underlying host graph is coloured with a set of colours (instead of just one colour). We give bounds for monochromatic tree covers in this setting, both for an underlying complete graph, and an underlying complete bipartite graph. We also discuss a generalisation of Ramsey numbers to our setting and propose some other new directions.Our results for tree covers in complete graphs imply that a stronger version of Ryser’s conjecture holds for $k$-intersecting $r$-partite $r$-uniform hypergraphs: they have a transversal of size at most $r?k$. (Similar results have been obtained by Király et al., see below.) However, we also show that the bound $r?k$ is not best possible in general.     

Flow-contractible configurations and group connectivity of signed graphs

Jaeger, Linial, Payan and Tarsi (JCTB, 1992) introduced the concept of group connectivity as a generalization of nowhere-zero flow for graphs. In this paper, we introduce group connectivity for signed graphs and establish some fundamental properties. For a finite abelian group $A$, it is proved that an $A$-connected signed graph is a contractible configuration for $A$-flow problem of signed graphs. In addition, we give sufficient edge connectivity conditions for signed graphs to be $A$-connected and study the group connectivity of some families of signed graphs.     

Graph coloring and Graham’s greatest common divisor problem

In this paper we introduce and study two graph coloring problems and relate them to some deep number-theoretic problems. For a fixed positive integer $k$ consider a graph $B_k$ whose vertex set is the set of all positive integers with two vertices $a,b$ joined by an edge whenever the two numbers $a∕gcd(a,b)$ and $b∕gcd(a,b)$ are both at most $k$. We conjecture that the chromatic number of every such graph $B_k$ is equal to $k$. This would generalize the greatest common divisor problem of Graham from 1970; in graph-theoretic terminology it states that the clique number of $B_k$ is equal to $k$. Our conjecture is connected to integer lattice tilings and partial Latin squares completions.     

Locating a robber with multiple probes

We consider a game in which a cop searches for a moving robber on a connected graph using distance probes, which is a slight variation on one introduced by Seager (2012). Carragher, Choi, Delcourt, Erickson and West showed that for any $n$-vertex graph $G$ there is a winning strategy for the cop on the graph $G^{1∕m}$ obtained by replacing each edge of $G$ by a path of length $m$, if $m\ge n$ (Carragher et al., 2012). The present authors showed that, for all but a few small values of $n$, this bound may be improved to $m\ge n∕2$, which is best possible (Haslegrave et al., 2016). In this paper we consider the natural extension in which the cop probes a set of $k$ vertices, rather than a single vertex, at each turn. We consider the relationship between the value of $k$ required to ensure victory on the original graph with the length of subdivisions required to ensure victory with $k=1$. We give an asymptotically best-possible linear bound in one direction, but show that in the other direction no subexponential bound holds. We also give a bound on the value of $k$ for which the cop has a winning strategy on any (possibly infinite) connected graph of maximum degree $\Delta$, which is best possible up to a factor of $(1?o\left(1\right))$.