Ma thèse vise à étudier des problématiques de recherche liées à l’étendue du second degré sortant dans les graphes orientés ainsi qu’aux méthodes probabilistes:
Dans un graphe orienté (D), le second degré sortant d’un sommet (x), noté d++(x), est le nombre de sommets y tels que d+(x,y)=2, où d+(x,y) désigne la longueur d’un plus court chemin orienté de x vers y, lorsqu’un tel chemin existe. Il est évident que la somme des premiers degrés sortants des sommets d’un graphe orienté n’est autre que le nombre de ses arcs. Contrairement au premier degré sortant, la somme des seconds degrés sortants des sommets, notée d++(D), n’est pas constante par rapport au nombre de sommets et d’arcs.
Dans ce contexte, nous cherchons l’ensemble des valeurs possibles de d++(D) parmi toutes les orientations D d’un graphe non orienté donné G, que nous appelons l’étendue d++ de G. Nous répondons à cette question pour les graphes complets en caractérisant, en fonction d’un entier n, les valeurs pouvant être prises par la somme des seconds degrés sortants des sommets d’un tournoi d’ordre n. Autrement dit, nous montrons que pour tout entier n ≥ 6, la somme des seconds degrés sortants dans un tournoi d’ordre n est égale à i si et seulement si i ∈ {0,..., n(n−1)/2} {1,2,4}.
De plus, nous caractérisons les tournois d’ordre n dont la somme des seconds degrés sortants est égale à i ∈ {0,3}. Ensuite, nous étudions la caractérisation des tournois d’ordre n ayant cette somme égale à i, pour 5 ≤ i ≤ n(n−1)/2.
Au cours des démonstrations de cette question, nous introduisons le nouveau concept de degré de roi (king degree) afin de résoudre le problème. Le degré de roi d’un sommet x est le nombre de sommets pouvant être atteints depuis x par un chemin orienté de longueur au plus 2. De plus, nous répondons à la question précédente pour 5 ≤ i ≤ 9 et déterminons le nombre de tels tournois en fonction de n. Le problème reste ouvert pour i ≥ 10.
Ensuite, nous donnons une description complète de l’étendue d++ pour les chemins et les cycles, et développons des outils généraux pour les graphes sans triangles. Comme applications, nous déterminons exactement l’étendue pour les graphes en grille et établissons les valeurs extrémales de d++(D) pour les arbres à l’aide de preuves constructives. Ces résultats constituent une base pour de futures recherches sur le problème de l’étendue d++ dans les graphes orientés, où plusieurs problèmes ouverts sont introduits.
Enfin, nous présentons plusieurs résultats probabilistes concernant la somme du second degré sortant dans certaines classes de graphes. En particulier, nous étudions son espérance et sa variance pour différentes orientations de graphes. Ces résultats permettent de mieux comprendre le comportement et la distribution de l’étendue du second degré sortant dans ces graphes. Nous établissons également plusieurs propriétés fondamentales utiles pour les analyses ultérieures.
En plus des résultats obtenus dans cette thèse, plusieurs questions restent ouvertes et font actuellement l’objet d’études. Certaines de ces directions de recherche en cours sont présentées à la fin de la thèse. |
My thesis aims to investigate research topics related to the second out-degree range in oriented graphs and probabilistic methods:
In an oriented graph D, the second out-degree of a vertex x, denoted by d++(x) , is the number of vertices y such that d+(x,y) = 2, where d+(x,y) is the length of a shortest xy directed path, if it exists. It is obvious that the sum of the first out-degrees of the vertices in an oriented graph is nothing but the number of its arcs. Unlike the first out-degree, the summation of the second out-degrees of the vertices, denoted by d++(D) is not constant with respect to the number of vertices and arcs.
In this context, we ask for the range of possible values of d++(D) over all
orientations D of a given undirected graph G, which we will call the d++-range of G, and answered it for complete graphs, by characterizing, as a function of some integer n, the values that can be the summation of the second out-degrees of the vertices in a tournament of order n. In other words, we showed that for any integer n ≥ 6, the summation of the second out-degrees in an n-tournament is i if and only if i ∈ {0,..., n(n−1)/2}{1,2,4}. Moreover, we characterized n-tournaments whose summation of second out-degrees is i ∈ {0,3}. Then
we asked for a characterization of n-tournaments having this summation i, 5 ≤ i ≤ n(n−1)/2.
Throughout the proofs of this question, we use the new concept of king degree in order to settle the problem; the king degree of a vertex x is the number of vertices that can be reached from x by a directed path of length at most 2. Moreover, we answered the above question for 5 ≤ i ≤ 9 and found the number of
such tournaments in terms of n. The problem is still open for i ≥ 10.
Then, we gave a complete description of the d++- range for paths and cycles,
and developed general tools for triangle-free graphs. As applications, we determined the exact range for grid graphs and established the extremal values of d++(D) for trees through constructive proofs. These results provide a foundation for further investigations of the d++-range problem in oriented graphs, where several open problems are introduced.
Finally, we present several probabilistic results concerning the sum of the d++
range in certain classes of graphs. In particular, we investigate its expected value and variance under different graph orientations. These results provide a better understanding of the behavior and distribution of the range of the second out-degree in these graphs. We also establish some fundamental properties that will be useful in the subsequent analysis.
In addition to the results obtained in this thesis, several questions remain open and are currently under investigation. Some of these ongoing research directions are presented at
the end of the thesis. |