Vertex and edge spread of zero forcing number,maximum nullity,and minimum rank of a graph

The minimum rank of a simple graph G is defined to be the smallest possible rank over all symmetric real matrices whose ijth entry (for $i\ne j$) is nonzero whenever $\{i\text{,}j\}$ is an edge in G and is zero otherwise; maximum nullity is taken over the same set of matrices. The zero forcing number is the minimum size of a zero forcing set of vertices and bounds the maximum nullity from above. The spread of a graph parameter at a vertex v or edge e of G is the difference between the value of the parameter on G and on $G-v$ or $G-e$. Rank spread (at a vertex) was introduced in [4]. This paper introduces vertex spread of the zero forcing number and edge spreads for minimum rank/maximum nullity and zero forcing number. Properties of the spreads are established and used to determine values of the minimum rank/maximum nullity and zero forcing number for various types of grids with a vertex or edge deleted.     

Invariant sets under permutation,extremal graphs,and covering codes

Let $c_q(n,R)$ denote the minimum cardinality of a subset H in ${\mathbb{F}}_q^n$ such that every word in this space differs in at most R coordinates from a multiple of a vector in H, where q is a prime or a prime power. In order to explore the symmetries of such coverings, we investigate a few algebraic properties of invariant sets under permutation. Extremal problems arising from invariant sets are also studied on a graph theoretical viewpoint. As an application, a new class of upper bounds on $c_q(n,R)$ is constructed.     

Forwarding and optical indices of 4-regular circulant networks

An all-to-all routing in a graph G is a set of oriented paths of G, with exactly one path for each ordered pair of vertices. The load of an edge under an all-to-all routing R is the number of times it is used (in either direction) by paths of R, and the maximum load of an edge is denoted by $\pi (G,R)$. The edge-forwarding index $\pi (G)$ is the minimum of $\pi (G,R)$ over all possible all-to-all routings R, and the arc-forwarding index $\overrightarrow{\pi }(G)$ is defined similarly by taking direction into consideration, where an arc is an ordered pair of adjacent vertices. Denote by $w(G,R)$ the minimum number of colours required to colour the paths of R such that any two paths having an edge in common receive distinct colours. The optical index $w(G)$ is defined to be the minimum of $w(G,R)$ over all possible R, and the directed optical index $\overrightarrow{w}(G)$ is defined similarly by requiring that any two paths having an arc in common receive distinct colours. In this paper we obtain lower and upper bounds on these four invariants for 4-regular circulant graphs with connection set $\{\pm 1,\pm s\}$, $1<s<n/2$. We give approximation algorithms with performance ratio a small constant for the corresponding forwarding index and routing and wavelength assignment problems for some families of 4-regular circulant graphs.     

Identifying defective sets using queries of small size

We examine the following version of a classic combinatorial search problem introduced by Rényi: Given a finite set $X$ of $n$ elements we want to identify an unknown subset $Y$ of $X$, which is known to have exactly $d$ elements, by means of testing, for as few as possible subsets $A$ of $X$, whether $A$ intersects $Y$ or not. We are primarily concerned with the non-adaptive model, where the family of test sets is specified in advance, in the case where each test set is of size at most some given natural number $k$. Our main results are nearly tight bounds on the minimum number of tests necessary when $d$ and $k$ are fixed and $n$ is large enough.     

Amélioration des bornes de la complexité bilinéaire de la multiplication dans certains corps finis

From the existence of a tower of algebraic function fields, we improve upper bounds on the bilinear complexity of multiplication in all extensions of the finite fields ${\mathbb{F}}_p$ and ${\mathbb{F}}_{p^2}$ where p is a prime ?5. In particular, we improve asymptotic upper bounds on this complexity for prime finite fields. To cite this article: S. Ballet, J. Chaumine, C. R. Acad. Sci. Paris, Ser. I 339 (2004).     

On the kernel size of clique cover reductions for random intersection graphs

Covering all edges of a graph by a minimum number of cliques is a well known $\mathsf{NP}$-hard problem. For the parameter k being the maximal number of cliques to be used, the problem becomes fixed parameter tractable. However, assuming the Exponential Time Hypothesis, there is no kernel of subexponential size in the worst-case.We study the average kernel size for random intersection graphs with n vertices, edge probability p, and clique covers of size k. We consider the well-known set of reduction rules of Gramm, Guo, Hüffner, and Niedermeier (2009) [17] and show that with high probability they reduce the graph completely if p is bounded away from 1 and $k<c\log n$ for some constant $c>0$. This shows that for large probabilistic graph classes like random intersection graphs the expected kernel size can be substantially smaller than the known exponential worst-case bounds.     

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.     

Universal arcs in local tournaments

An arc $uv$ of a digraph $D$ is called universal if $uv$ and $w$ are in a common cycle for any vertex $w$ of $D$. In this paper we characterize local tournaments whose every arc is universal.     

Throttling for the game of Cops and Robbers on graphs

We consider the cop-throttling number of a graph $G$ for the game of Cops and Robbers, which is defined to be the minimum of $(k+{\mathrm{capt}}_k\left(G\right))$, where $k$ is the number of cops and ${\mathrm{capt}}_k\left(G\right)$ is the minimum number of rounds needed for $k$ cops to capture the robber on $G$ over all possible games. We provide some tools for bounding the cop-throttling number, including showing that the positive semidefinite (PSD) throttling number, a variant of zero forcing throttling, is an upper bound for the cop-throttling number. We also characterize graphs having low cop-throttling number and investigate how large the cop-throttling number can be for a given graph. We consider trees, unicyclic graphs, incidence graphs of finite projective planes (a Meyniel extremal family of graphs), a family of cop-win graphs with maximum capture time, grids, and hypercubes. All the upper bounds on the cop-throttling number we obtain for families of graphs are $O\left(\sqrt{n}\right)$.