Thesis title: The Second Out-Degree Range in Oriented Graphs and Probabilistic Methods.

My thesis aims to investigate the following topics:

Topic 1: The Second Out-Degree Range in Oriented Graphs.

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, 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.

Topic 1: Probabilistic Methods.

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.

Aya Alhussein and Ayman El Zein, The King Degree and the Second Out-Degree of Tournaments, Discrete Math. 348 (9) (2025) 114497.

1- Delivered a Seminar on Graph Theory titled by "The King Degree and the Second Out-Degree of Tournaments", on 18 April 2024, at the Lebanese University-Faculty of Sciences, Department of Mathematics, KALMA Laboratory, Beirut.

2- Delivered a Seminar on Graph Theory titled by "The d⁺⁺ range problem in oriented graphs", on 31 January 2026, at Université Côte d’Azur, Laboratoire I3S, Sophia Antipolis-France.

3- Delivered a Seminar on Graph Theory titled by "The d⁺⁺ range problem in oriented graphs", on 3 February 2026, at UFR Informatique - IRIF, Paris-France.

4- Delivered a Seminar on Graph Theory titled by "The d⁺⁺ range problem in oriented graphs", on 5 February 2026, at Université Bourgogne Europe, LIB laboratory, Dijon-France.

5- Delivered a Seminar on Graph Theory titled by "The d⁺⁺ range problem in oriented graphs", on 31 July 2026, at the Lebanese University-Faculty of Sciences, Department of Mathematics, KALMA Laboratory, Beirut.