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]

The k-restricted edge-connectivity of a graph G , denoted by λ k ( G ) , is defined as the minimum size of an edge set whose removal leaves exactly two connected components each containing at least k vertices. This graph invariant, which can be seen as a generalization of a minimum edge-cut, has been extensively studied from a combinatorial point of view. However, very little is known about the complexity of computing λ k ( G ) . Very recently, in the parameterized complexity community the notion of good edge separation of a graph has been defined, which happens to be essentially the same as the k -restricted edge-connectivity. Motivated by the relevance of this invariant from both combinatorial and algorithmic points of view, in this article we initiate a systematic study of its computational complexity, with special emphasis on its parameterized complexity for several choices of the parameters. We provide a number of NP -hardness and W [1]-hardness results, as well as FPT -algorithms. [ABSTRACT FROM AUTHOR]

Let r ( G , H ) be the smallest integer N such that for any 2 -coloring (say, red and blue) of the edges of K n , n ⩾ N , there is either a red copy of G or a blue copy of H . Let K n − K 1 , s be the complete graph on n vertices from which the edges of K 1 , s are dropped. In this note we present exact values for r ( K m − K 1 , 1 , K n − K 1 , s ) and new upper bounds for r ( K m , K n − K 1 , s ) in numerous cases. We also present some results for the Ramsey number of Wheels versus K n − K 1 , s . [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]

A connected covering is a design system in which the corresponding block graph is connected. The minimum size of such coverings are called connected coverings numbers. In this paper, we present various formulas and bounds for several parameter settings for these numbers. We also investigate results in connection with Turán systems. Finally, a new general upper bound, improving an earlier result, is given. The latter is used to improve upper bounds on a question concerning oriented matroid due to Las Vergnas. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the Möbius function μ S associated to a (locally finite) poset arising from a semigroup S of Z m . We introduce and develop a new approach to study μ S by using the Hilbert series of S . The latter enables us to provide formulas for μ S when S belongs to certain families of semigroups. Finally, a characterization for a locally finite poset to be isomorphic to a semigroup poset is given. [ABSTRACT FROM AUTHOR]

Abstract: Let be a -connected graph. is called -optimal, if its -restricted edge-connectivity equals its minimum -edge degree.  is called super- if every -cut isolates a connected subgraph of order . Firstly, we give a lower bound on the order of -fragments in triangle-free graphs that are not -optimal. Secondly, we present an Ore-type condition for triangle-free graphs to be -optimal. Thirdly, we prove a lower bound on the order of -fragments in triangle-free -connected graphs, and use it to show that triangle-free graphs with high minimum degree are -optimal and super-. [Copyright &y& Elsevier]