Search

AbstractA classic result in Euclidean geometry asserts that every non-collinear set of n points in the Euclidean plane determines at least n distinct lines. Chen and Chvátal conjectured that this holds for an arbitrary finite metric space, with an appropriate definition of line. This conjecture remains open even for graph metrics. In this paper, sufficient conditions on the girth to guarantee that a graph satisfies the conjecture are stated. We first study the existence of a universal line generated by an edge. Then, we focus on graphs of order n and maximum girth g with respect to their radius r. We prove that graphs with minimum degree δ ≥ 4 and girth g = 2r+1 or g = 2r have at least n distinct lines and we also partially solve the case when δ = 3. Graphs with cut-vertices are also studied, providing several upper bounds on the diameter, in terms of the girth, in order to assure that the graph satisfies the Chen-Chvátal conjecture. Finally, we prove that any triangle-free graph of order n, diameter 3 and minimum degree δ ≥ 4 has more than n distinct lines and we also partially solve the case when δ = 3. [ABSTRACT FROM AUTHOR]

A wide range of parameters of domination in graphs can be defined and studied through a common approach that was recently introduced in [] under the name of w-domination, where w = (w 0 , w 1 , ⋯ , w l) is a vector of non-negative integers such that w 0 ≥ 1 . Given a graph G, a function f : V (G) ⟶ { 0 , 1 , ⋯ , l } is said to be a w-dominating function if ∑ u ∈ N (v) f (u) ≥ w i for every vertex v with f (v) = i , where N(v) denotes the open neighbourhood of v ∈ V (G) . The weight of f is defined to be ω (f) = ∑ v ∈ V (G) f (v) , while the w-domination number of G, denoted by γ w (G) , is defined as the minimum weight among all w-dominating functions on G. A wide range of well-known domination parameters can be defined and studied through this approach. For instance, among others, the vector w = (1 , 0) corresponds to the case of standard domination, w = (2 , 1) corresponds to double domination, w = (2 , 0 , 0) corresponds to Italian domination, w = (2 , 0 , 1) corresponds to quasi-total Italian domination, w = (2 , 1 , 1) corresponds to total Italian domination, w = (2 , 2 , 2) corresponds to total { 2 } -domination, while w = (k , k - 1 , ⋯ , 1 , 0) corresponds to { k } -domination. In this paper, we show that several domination parameters of lexicographic product graphs G ∘ H are equal to γ w (G) for some vector w ∈ { 2 } × { 0 , 1 , 2 } l and l ∈ { 2 , 3 } . The decision on whether the equality holds for a specific vector w will depend on the value of some domination parameters of H. In particular, we focus on quasi-total Italian domination, total Italian domination, 2-domination, double domination, total { 2 } -domination, and double total domination of lexicographic product graphs. [ABSTRACT FROM AUTHOR]

We study the existence and the number of k -neighborly reorientations of an oriented matroid. This leads to k -variants of McMullen's problem and Roudneff's conjecture, the case k = 1 being the original statements. Adding to results of Larman and García-Colín, we provide new bounds on k -McMullen's problem and prove the conjecture for several ranks and k by computer. Further, we show that k -Roudneff's conjecture for fixed rank and k reduces to a finite case analysis. As a consequence we prove the conjecture for odd rank r and k = r − 1 2 as well as for rank 6 and k = 2 with the aid of the computer. [ABSTRACT FROM AUTHOR]

In Chomp on graphs, two players alternatingly pick an edge or a vertex from a graph. The player that cannot move any more loses. The questions one wants to answer for a given graph are: Which player has a winning strategy? Can an explicit strategy be devised? We answer these questions (and determine the Nim-value) for the class of generalized Kneser graphs and for several families of Johnson graphs. We also generalize some of these results to the clique complexes of these graphs. Furthermore, we determine which player has a winning strategy for some classes of threshold graphs. [ABSTRACT FROM AUTHOR]