Identifying codes with small radius in some infinite regular graphs.
General bounds for identifying codes in some infinite regular graphs.
Structural properties of twin-free graphs.
Ordres médians et ordres de Slater des tournois
Dans cet article, nous essayons de faire le point sur les résultats concernant les aspects combinatoires et algorithmiques des ordres médians et des ordres de Slater des tournois. La plupart des résultats recensés sont tirés de différentes publications ; plusieurs sont originaux.
Utilisation des scores dans des méthodes exactes déterminant les ordres médians de tournois
Dans cet article, nous utilisons un paramètre défini à partir des scores d’un tournoi pour déterminer les ordres médians de . Ce paramètre évalue un éloignement entre le tournoi et les tournois transitifs ayant le même nombre de sommets. Appelant le nombre minimum d’arcs à inverser pour rendre transitif, et le nombre de sommets de , nous proposons d’abord deux algorithmes linéaires en n calculant et un ordre médian de pour les tournois tels que soit égal à ou . Puis nous...
Encadrement de l'indice de slater d'un tournoi à l'aide de ses scores
Dans cet article, nous définissons un paramètre à partir des scores d’un tournoi . Ce paramètre évalue un éloignement entre le tournoi et les tournois transitifs de même ordre. Appelant le nombre minimum d’arcs à inverser pour rendre transitif, nous montrons que l’on a . Nous déterminons ensuite des bornes sur la valeur maximum de pour les tournois à donné. Nous en déduisons enfin, en fonction du nombre de sommets de et de , un encadrement de l’indice de Slater d’un tournoi quelconque....
Foreword
On the existence of a cycle of length at least 7 in a (1,≤ 2)-twin-free graph
We consider a simple, undirected graph G. The ball of a subset Y of vertices in G is the set of vertices in G at distance at most one from a vertex in Y. Assuming that the balls of all subsets of at most two vertices in G are distinct, we prove that G admits a cycle with length at least 7.
Page 1