If G is a simple graph and ρ ∈ [ 0 , 1 ] , the reliability R G ( ρ ) is the probability of G being connected after each of its edges is removed independently with probability ρ . A simple graph G is a uniformly most reliable graph (UMRG) if R G ( ρ ) ≥ R H ( ρ ) for every ρ ∈ [ 0 , 1 ] and every simple graph H on the same number of vertices and edges as G . Boesch (1986) conjectured that, if n and m are such that there exists a connected simple graph on n vertices and m edges, then there also exists a UMRG on the same number of vertices and edges. Some counterexamples to Boesch’s conjecture were given by Kelmans, Myrvold et al., and Brown and Cox. It is known that Boesch’s conjecture holds whenever the corank, defined as c = m − n + 1 , is at most 4 (and the corresponding UMRGs are fully characterized). Ath and Sobel conjectured that Boesch’s conjecture holds whenever the corank c is between 5 and 8, provided the number of vertices is at least 2 c − 2 . In this work, we give an infinite family of counterexamples to Boesch’s conjecture of corank 5. These are the first reported counterexamples that attain the minimum possible corank. As a byproduct, the conjecture by Ath and Sobel is disproved.

Abstract

An induced matching of a graph is a set of edges, no two of which share an endpoint or are joined by an edge of the graph. The Maximum Induced Matching problem asks for finding an induced matching of maximum cardinality. Solving this problem for a graph G is equivalent to finding a maximum independent set in L(G) 2 , the square of the line graph of G . Gartland and Lokshtanov [2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) (2020), pp. 613-624] proved that the problem of finding a maximum independent set can be solved in quasi-polynomial time in the class of all P k -free graphs, for each fixed k. Therefore, the Maximum Induced Matching problem can be solved in quasi-polynomial time in the class G k , which consists of all graphs G such that L(G) 2 is P k -free, for each fixed k. In this work, we give a complete characterization of the class G k by minimal forbidden induced subgraphs, for each fixed k. Our main result is a complete description, for each fixed k , of the family F k , of minimal forbidden induced subgraphs of G k , as consisting precisely of those graphs associated with the strings accepted by a certain deterministic finite automaton. Our results improve upon an earlier characterization by forbidden induced subgraphs of G k due to Hatzel and Wiederrecht [Graph-theoretic concepts in computer science (2018), pp. 252-265].

A graph is balanced when its clique matrix is balanced. Bonomo, Durán, Lin and Szwarcfiter (2006) proved that a graph is balanced if and only if it contains no induced subgraphs known as extended odd suns. However, a characterization of balanced graphs by minimal forbidden induced subgraphs is not known. In this work, we find such a characterization when restricted to the class of claw-free graphs. As a consequence, we prove that there is an O(m2 + n)-time algorithm that, given any graph, either decides that it is balanced or gives a certificate of the fact that it is not claw-free balanced.

If G is a simple graph and ρ ϵ [0, 1], the reliability Rg(ρ) is the probability of G being connected after each of its edges is removed independently with probability ρ. A simple graph G is a uniformly most reliable graph (UMRG) if Rg(ρ) ≥ Rh(ρ) for every ρ ϵ [0, 1] and every simple graph H on the same number of vertices and edges as G. Boesch [J. Graph Theory 10 (1986), 339-352] conjectured that, if n and m are such that there exists a connected simple graph on n vertices and m edges, then there also exists a UMRG on the same number of vertices and edges. Some counterexamples to Boesch's conjecture were given by Kelmans, Myrvold et al., and Brown and Cox. It is known that Boesch's conjecture holds whenever the corank, defined as c = m - n + 1, is at most 4 (and the corresponding UMRGs are fully characterized). Ath and Sobel conjectured that Boesch's conjecture holds whenever the corank c is between 5 and 8, provided the number of vertices is at least 2c - 2. In this work, we give an infinite family of counterexamples to Boesch's conjecture of corank 5. These are the first reported counterexamples that attain the minimum possible corank. As a byproduct, the conjecture by Ath and Sobel is disproved.

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). In the present work, 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.

This article is devoted to the study of two arithmetical sources associated with classical partitions, that are both defined through the mediant of two fractions. The Stern-Brocot source is associated with the sequence of all the mediants, while the Sturm source only keeps mediants whose denominator is "not too large". Even though these sources are both of zero Shannon entropy, with very similar Renyi entropies, their probabilistic features yet appear to be quite different. We then study how they influence the behaviour of tries built on words they emit, and we notably focus on the trie depth. The paper deals with Analytic Combinatorics methods, and Dirichlet generating functions, that are usually used and studied in the case of good sources with positive entropy. To the best of our knowledge, the present study is the first one where these powerful methods are applied to a zero-entropy context. In our context, the generating function associated with each source is explicit and related to classical functions in Number Theory, as the ζ function, the double ζ function or the transfer operator associated with the Gauss map. We obtain precise asymptotic estimates for the mean value of the trie depth that prove moreover to be quite different for each source. Then, these sources provide explicit and natural instances which lead to two unusual and different trie behaviours.