Discrete Mathematics & Theoretical Computer Science |

Let $t$ be a positive real number. A graph is called $t$-tough if the removalof any vertex set $S$ that disconnects the graph leaves at most $|S|/t$components, and all graphs are considered 0-tough. The toughness of a graph isthe largest $t$ for which the graph is $t$-tough, whereby the toughness ofcomplete graphs is defined as infinity. A graph is minimally $t$-tough if thetoughness of the graph is $t$, and the deletion of any edge from the graphdecreases the toughness. In this paper, we investigate the minimum degree andthe recognizability of minimally $t$-tough graphs in the classes of chordalgraphs, split graphs, claw-free graphs, and $2K_2$-free graphs.

We define a q-linear path in a hypergraph H as a sequence (e_1,...,e_L) of edges of H such that |e_i ∩ e_i+1 | ∈ [[1, q]] and e_i ∩ e_j = ∅ if |i − j| > 1. In this paper, we study the connected components associated to these paths when q = k − 2 where k is the rank of H. If k = 3 then q = 1 which coincides with the well-known notion of linear path or loose path. We describe the structure of the connected components, using an algorithmic proof which shows that the connected components can be computed in polynomial time. We then mention two consequences of our algorithmic result. The first one is that deciding the winner of the Maker-Breaker game on a hypergraph of rank 3 can be done in polynomial time. The second one is that tractable cases for the NP-complete problem of "Paths Avoiding Forbidden Pairs" in a graph can be deduced from the recognition of a special type of line graph of a hypergraph.

Inspired by the split decomposition of graphs and rank-width, we introducethe notion of $r$-splits. We focus on the family of $r$-splits of a graph oforder $n$, and we prove that it forms a hypergraph with several properties. Weprove that such hypergraphs can be represented using only $\mathcal O(n^{r+1})$of its hyperedges, despite its potentially exponential number of hyperedges. Wealso prove that there exist hypergraphs that need at least $\Omega(n^r)$hyperedges to be represented, using a generalization of set orthogonality.

Given a set system $\mathcal{X} = \{\mathcal{U},\mathcal{S}\}$, where$\mathcal{U}$ is a set of elements and $\mathcal{S}$ is a set of subsets of$\mathcal{U}$, an exact hitting set $\mathcal{U}'$ is a subset of $\mathcal{U}$such that each subset in $\mathcal{S}$ contains exactly one element in$\mathcal{U}'$. We refer to a set system as exactly hittable if it has an exacthitting set. In this paper, we study interval graphs which have intersectionmodels that are exactly hittable. We refer to these interval graphs as exactlyhittable interval graphs (EHIG). We present a forbidden structurecharacterization for EHIG. We also show that the class of proper intervalgraphs is a strict subclass of EHIG. Finally, we give an algorithm that runs inpolynomial time to recognize graphs belonging to the class of EHIG.