If is a simple connected graph with the vertex set and the edge set , S is a subset of , and let be the set of neighbors of S in . Then, the differential of S is defined as . The differential of G, denoted by , is the maximum value of for all subsets . The graph operator is defined as the graph that results by subdividing every edge of G once and joining pairs of these new vertices iff their corresponding edges are incident in G. In this paper, we study the relations between and . Besides, we exhibit some results relating the differential and well-known graph invariants, such as the domination number, the independence number, and the vertex-cover number.
Let P be a set of points in general position in the plane. The edge disjointness graph of P is the graph whose vertices are the closed straight line segments with endpoints in P, two of which are adjacent in if and only if they are disjoint. In this paper we show that the connectivity of is at most , and that this upper bound is asymptotically tight. The proof is based on the analysis of the connectivity of , where denotes an n-point set that is almost 3-symmetric.
1 August 2013 in European Journal of Combinatorics