A complete \(k\)-vertex-coloring of a graph \(G\) is a vertex-coloring of \(G\) using \(k\) colors such that for every pair of colors there is at least two incident vertices in \(G\) colored with this pair of colors. The \emph{chromatic} \(\chi(G)\) and \emph{achromatic} \(\alpha(G)\) numbers of \(G\) are the smallest and the largest number of colors in a complete proper \(k\)-vertex-coloring of \(G\), therefore \(\chi(G)\leq\alpha(G)\).

The dichromatic number and the diachromatic number, generalice the concepts of chromatic number and achromatic number. An acyclic \(k\)-vertex-coloring of a digraph \(D\) is vertex coloring using \(k\) colors such that \(D\) has no monochromatic cycles and a \emph{complete} \(k\)-vertex-coloring of a digraph \(D\) is a vertex coloring using \(k\) colors such that for every ordered pair \((i,j)\) of different colors, there is at least one arc \((u,v)\) such that \(u\) has color \(i\) and \(v\) has color \(j\). The dichromatic number \(dc(D)\) and diachromatic number \(dac(D)\) of \(D\) are the smallest and the largest number of colors in a complete proper \(k\)-vertex-coloring of \(D\), therefore \(dc(D)\leq dac(D)\).

We determine the achromatic and diachromatic numbers of some specific circulant graphs and digraphs and give general bounds for these two parameters on these graphs and digraphs. Also, we determine the achromatic index for circulant graphs of order \(q^2+q+1\) using projective planes.

Joint work with: Juan José Montellano-Ballesteros, Mika Olsen and Christian Rubio-Montiel.

An \((r, l)\)-partition of a graph \(G\) is a partition of its vertex set into \(r\) independent sets and \(l\) cliques. A graph is \((r,l)\) if it admits an \((r, l)\)-partition. A graph is well-covered if every maximal independent set is also maximum. A graph is \((r,l)\)-well-covered if it is both \((r,l)\) and well-covered. We have proved the full classification of the decision problem \((r,l)\)-Well-Covered Graph problem, where we are given a graph \(G\), and the question is whether \(G\) is an \((r, l)\)-well-covered graph. We have shown that this problem is polynomial only in the cases \((0, 1)\), \((0, 2)\), \((1, 0)\), \((1, 1)\), \((1, 2)\), and \((2, 0)\) and hard otherwise. The Sandwich Problem for the Property \(\pi\) has as an instance a pair of graphs \(G1 = (V, E_1)\) and \(G2 = (V, E_2)\) with \(E_1 \subset E_2\), plus the question whether there is a graph \(G=(V,E)\) with \(E_1 \subset E\subset E_2\), such that \(G\) has the property \(\pi\). When a recognition problem for a property \(\pi\) is hard, we can consider the sets \(E_1 = E_2\) to obtain that the sandwich problem for the property \(\pi\) reduces to the recognition and so also hard. Hence, the only cases where the \((r, l)\)-well-covered sandwich problem can be no longer hard are in the \(6\) polynomial cases. In this talk we prove that \((r, l)\)-well-covered sandwich problem is polynomial in the cases that \((r, l) = (0, 1), (1, 0), (1, 1)\) or \((0, 2)\), and NP-complete if we consider the property of being \((1, 2)\)-well-covered.

This work was done with the collaboration of Sancrey Rodrigues Alves (FAETEC), Fernanda Couto (UFRRJ), Luerbio Faria (UERJ), Sylvain Gravier (CNRS), and Uéverton S. Souza (UFF).

An \((n,k,\lambda)\) perfect sequence covering array is a subset of the \(n!\) permutations of the sequence \((1, 2, \dots, n)\) whose elements collectively contain each ordered \(k\)-subsequence exactly \(\lambda\) times. The central question is: for given \(n\) and \(k\), what is the smallest value of \(\lambda\) (denoted \(g(n,k)\)) for which such a configuration exists? We interpret the sequences of a perfect sequence covering array as elements of the symmetric group \(S_n\), and constrain its structure to be a union of cosets of a prescribed subgroup of \(S_n\). By adapting a search algorithm due to Mathon and van Trung for finding spreads, we obtain highly structured examples of perfect sequence covering arrays. In particular, we determine that \(g(6,3) = g(7,3) = g(7,4) = 2\) and that \(g(8,3)\) is either 2 or 3.

This is joint work with Jingzhou Na.

Given a set (known to us), and a partition of this set, unknown to us, consider the following task. We have to determine the partition by making successive queries about pairs of elements, each time querying whether the pair belong to the same class or not. Later queries are allowed to depend on the outcome of earlier queries. There is a natural way to assign a graph to each step of the querying process, by starting with an edgeless graph where each vertex represents an element of the set, and after queries identifying vertices for a yes-answer and adding edges for no-answers. We prove the at first sight surprising result that the partitioning algorithms reaching the minimal average number of queries are exactly those that keep these graphs chordal. (The average is taken over all possible partitions of the base set.) The optimal algorithms even share the same distribution on the number of queries, which we characterize. We also analyse a related model where the number of partition classes is fixed, and each element of the base set chooses its partition class randomly.

This is joint work with Élie de Panafieu, Quentin Lutz and Alex Scott.

Spectral graph theory aims to extract structural information about graphs from spectra of different types of matrices associated with them, such as the adjacency matrix, Laplacian matrices, and many others. A basic step in any such application consists of computing or approximating the spectrum or some prescribed subset of eigenvalues. One strategy for this is to compute diagonal matrices that are congruent to the original matrices, which can be done quite efficiently if we have a graph decompositions such as the tree decomposition with bounded width. To be precise, let \(M=(m_{ij})\) be a symmetric matrix of order \(n\) whose elements lie in an arbitrary field \(\mathbb{F}\), and let \(G\) be the graph with vertex set \(\{1,\ldots,n\}\) such that distinct vertices \(i\) and \(j\) are adjacent if and only if \(m_{ij} \neq 0\). We present an algorithm that finds a diagonal matrix that is congruent to \(M\) in time \(O(k^2 n)\), provided that we are given a suitable tree decomposition of \(G\) with width \(k\). In addition to the above applications, this allows one to compute the determinant and to find the rank of a symmetric matrix in time \(O(k^2 n)\).

This is joint work with M. FŸrer (Pennsylvannia State University) and Vilmar Trevisan (Universidade Federal do Rio Grande do Sul).

In 1969, Tucker characterized proper circular-arc graphs as those graphs whose augmented adjacency matrices have the circularly compatible ones property. Moreover, he also found a polynomial-time algorithm for deciding whether any given augmented adjacency matrix has the circularly compatible ones property. These results led to the first polynomial-time recognition algorithm for proper circular-arc graphs. However, as remarked there, this work did not solve the problems of finding a structure theorem and an efficient recognition algorithm for the circularly compatible ones property in arbitrary matrices (i.e., not restricted to augmented adjacency matrices only). We solve these problems. More precisely, we give a minimal forbidden submatrix characterization for the circularly compatible ones property in arbitrary matrices and a linear-time recognition algorithm for the same property. We derive these results from analogous ones for the related \(D\)-circular property. Interestingly, these results lead to a minimal forbidden induced subgraph characterization and a linear-time recognition algorithm for proper circular-arc bigraphs, solving a problem first posed by Basu et al. [J. Graph Theory, 73 (2013), pp. 361--376]. Our findings generalize some known results about \(D\)-interval hypergraphs and proper interval bigraphs.

Cover-free families (CFFs) have been investigated under different names and as a solution to many problems related to combinatorial group testing. A \(d\)-cover-free family \(d\)-CFF\((t, n)\) is a set system with n subsets of a \(t\)-set, where the union of any d subsets does not contain any other. A \(d\)-CFF\((t, n)\) allows for the identification of up to \(d\) defective elements in a set of \(n\) elements by performing only \(t\) tests (typically \(t \ll n\)).

We explore different aspects of cover-free families in order to achieve fault tolerance in cryptography. For instance, while CFFs are used as a solution to many problems in this area, we note that some of those problems require CFFs with increasing \(n\). In this context, we investigate new infinite families and their constructions in order to better approach fault tolerance in cryptography. This is joint work with Lucia Moura.

[1] IDALINO, T. B.; MOURA, L., Nested cover-free families for unbounded fault-tolerant aggregate signatures. Theoretical Computer Science, 854 (2021), 116--130.
[2] IDALINO, T. B.; MOURA, L., Embedding cover-free families and cryptographical applications. Advances in Mathematics of Communications, 13 (2019), 629--643.

In the Euclidean plane, it is a well-known result that a set of n points defines exactly \(n(n-1)/2\) distinct segments, at least \(2(n-1)-1\) different rays and, when the points are not collinear, at least \(n\) different lines. Segments, rays and lines can be define in any quasimetric space by using its quasimetric. In this talk we survey recent results concerning the generalization of the above mentioned properties of the Euclidean plane, specially those of lines, to finite quasimetric spaces, mainly those defined by connected graphs and strongly connected digraphs.

In this talk, we explore combinatorial arrays that are useful in identifying faulty interactions in complex engineered systems. A separating hash family \({\sf SHF}_\lambda(N; k,v,\{w_1,\dots,w_s\})\) is an \(N \times k\) array on \(v\) symbols, with the property that no matter how disjoint sets \(C_1, \dots, C_s\) of columns with \(|C_i| = w_i\) are chosen, there are at least \(\lambda\) rows in which, for every \(1 \leq i < j \leq s\), no entry in a column of \(C_i\) equals that in a column of \(C_j\). (That is, there are \(\lambda\) rows in which sets \(\{C_1,\dots,C_s\}\) are separated) Separating hash families have numerous applications in combinatorial cryptography and in the construction of various combinatorial arrays; typically, one only considers whether two symbols are the same or different. We instead employ symbols that have algebraic significance.

We consider an \({\sf SHF}_\lambda(N; k,q^s,\{w_1,\dots,w_s\})\) whose symbols are column vectors from \({\mathbb F}_q^s\). The entry in row \(r\) and column \(c\) of the \({\sf SHF}\) is denoted by \({\bf v}_{r,c}\). Suppose that \(C_1, \dots, C_s\) is a set of disjoint sets of columns. Row \(r\) is covering for \(\{C_1, \dots, C_s\}\) if, whenever we choose \(s\) columns \(\{ \gamma_i \in C_i : 1 \leq i \leq s\}\), the \(s \times s\) matrix \([ {\bf v}_{r,\gamma_1} \cdots {\bf v}_{r,\gamma_s} ]\) is nonsingular over \({\mathbb F}_q\). Then the \({\sf SHF}_\lambda(N; k,q^s,\{w_1,\dots,w_s\})\) is covering if, for every way to choose \(\{C_1, \dots, C_s\}\), there are at least \(\lambda\) covering rows.

We establish that covering separating hash families of type \(1^t d^1\) give an effective construction for detecting arrays, which are useful in screening complex systems to find interactions among \(t\) or fewer factors without being masked by \(d\) or fewer other interactions. This connection easily accommodates outlier and missing responses in the screening. We explore asymptotic existence results and explicit constructions using finite geometries for covering separating hash families. We develop randomized and derandomized construction algorithms and discuss consequences for detecting arrays. This is joint work with Violet R. Syrotiuk (ASU).

The reliability polynomial of a simple graph G represents the probability that G will remain connected given a fixed probability \(1-p\) of each edge failing. A graph \(G\) is uniformly most reliable if its reliability polynomial is greater than or equal to the reliability polynomial of all other graphs with the same number of nodes and edges for all \(p \in [0, 1]\).

Which is the most-reliable graph with n nodes and m edges?

This problem has several variants, according to the notion of optimality (in a local or uniform sense), failure type (either nodes or edges), or reliability model (all-terminal connectedness, source-terminal or general multi-terminal setting).

This presentation shows a summary of the multiple proposals to attack the problem, together with recent trends and important conjectures proposed decades ago which require further research.

Particularly, we will present recently proved conjectures regarding UMGR (Uniformly Most-Reliable Graphs) as well as new evaluation techniques for this property.

Keywords: uniformly most-reliable graph, uniformly least-reliable graph, all-terminal reliability, source-terminal reliability, failure-type, graph theory.

Given a graph \(G\) and a set \(S \subseteq V(G)\), the \(\Delta\)-interval of \(S\), \([S]_{\Delta}\), is the set formed by the vertices of \(S\) and every \(w \in V(G)\) forming a triangle with two vertices of \(S\). If \([S]_\Delta = S\), then \(S\) is \(\Delta\)-convex of \(G\); if \([S]_{\Delta} = V(G)\), then \(S\) is a \(\Delta\)-interval set of \(G\). The \(\Delta\)-interval number of \(G\) is the minimum cardinality of a \(\Delta\)-interval set and the \(\Delta\)-convexity number of \(G\) is the maximum cardinality of a proper \(\Delta\)-convex subset of \(V(G)\). In this work, we show that the problem of computing the \(\Delta\)-convexity number is {\sf W}[1]-hard and {\sf NP}-hard to approximate within a factor \(O(n^{1-\varepsilon})\) for any constant \(\varepsilon > 0\) even for graphs with diameter \(2\) and that the problem of computing the \(\Delta\)-interval number is {\sf NP}-complete for general graphs. For the positive side, we present characterizations that lead to polynomial-time algorithms for computing the \(\Delta\)-convexity number of chordal graphs and for computing the \(\Delta\)-interval number of block graphs. We also present results on the \(\Delta\)-hull, \(\Delta\)-interval and \(\Delta\)-convexity numbers concerning the three standard graph products, namely, the Cartesian, strong and lexicographic products, in function of these and well-studied parameters of the operands.

Joint work with: Bijo S. Anand, Prasanth G. Narasimha-Shenoi, and Sabeer S. Ramla.

Ramsey's theorem states that, for any integer \(t\), if \(n\) is a sufficiently large integer, then every \(2\)-edge-coloring of a complete graph \(K_n\) contains a monochromatic \(K_t\). On the other hand, Turán's theorem says that, if a graph has sufficiently many edges, then it contains a \(K_t\) as a subgraph. In relation to these two types of problems, we study which \(2\)-colored patterns are forced to appear in differently saturated \(2\)-edge-colorings of the complete graph \(K_n\) provided \(n\) is large enough. This is a joint work with Yair Caro and Amanda Montejano.