Ramsey-Type Results for Geometric Graphs, I

For any 2-coloring of the segments determined by n points in general position in the plane, at least one of the color classes contains a non-self-intersecting spanning tree. Under the same assumptions, we also prove that there exist pairwise disjoint segments of the same color, and this bound is tight. The above theorems were conjectured by Bialostocki and Dierker. Furthermore, improving an earlier result of Larman et al., we construct a family of m segments in the plane, which has no more than members that are either pairwise disjoint or pairwise crossing. Finally, we discuss some related problems and generalizations. Received October 17, 1995, and in revised form February 10, 1996.     

极大非独立集可削去的因子临界图

如果对一个简单图G的每一个与G的顶点数同奇偶的独立集I，都有G-I有完美匹配，则称G是独立集可削去的因子临界图．如果图G不是独立集可削去的因子临界图，而对任意两个小相邻的顶点x与y，G xy足独立集可削去的因子临界图，则称G足极大非独立集可削去的因子临界图，本刻画了极大非独立集可削去的因子临界图。     

门槛图与度极大图

证明了门槛图与度极大图是一类图的两种不同说法,同时用图的对角限制极左矩阵刻画这一类图的结构。     

Maximal Energy Bipartite Graphs

 Given a graph G, its energy E(G) is defined to be the sum of the absolute values of the eigenvalues of G. This quantity is used in chemistry to approximate the total π-electron energy of molecules and in particular, in case G is bipartite, alternant hydrocarbons. Here we show that if G is a bipartite graph with n vertices, then

Cores of Geometric Graphs

Cameron and Kazanidis have recently shown that rank-three graphs are either cores or have complete cores, and they asked whether this holds for all strongly regular graphs. We prove that this is true for the point graphs and line graphs of generalized quadrangles and that when the number of points is sufficiently large, it is also true for the block graphs of Steiner systems and orthogonal arrays.     

Upper Maximal Graphs of Posets

We introduce and study a class of simple graphs, the upper-maximal graphs (UM-graphs), associated to finite posets. The vertices of the UM-graph of a given poset P are the elements of P, and edges are formed by those vertices x and y whenever any maximal element of P that is greater than x is also greater than y or vise versa. We show that the class of UM-graphs constitutes a subclass of comparability graphs. We further provide a characterization of chordal UM-graphs, and compare UM-graphs with known bound graphs of posets.     

Infinite Random Geometric Graphs

We introduce a new class of countably infinite random geometric graphs, whose vertices V are points in a metric space, and vertices are adjacent independently with probability p ? (0, 1){p \in (0, 1)} if the metric distance between the vertices is below a given threshold. For certain choices of V as a countable dense set in \mathbbRⁿ{\mathbb{R}^n} equipped with the metric derived from the L _∞-norm, it is shown that with probability 1 such infinite random geometric graphs have a unique isomorphism type. The isomorphism type, which we call GR _n , is characterized by a geometric analogue of the existentially closed adjacency property, and we give a deterministic construction of GR _n . In contrast, we show that infinite random geometric graphs in \mathbbR²{\mathbb{R}^{2}} with the Euclidean metric are not necessarily isomorphic.     

On Locally Gabriel Geometric Graphs

Let \(P\) be a set of \(n\) points in the plane. A geometric graph \(G\) on \(P\) is said to be locally Gabriel if for every edge \((u,v)\) in \(G\), the Euclidean disk with the segment joining \(u\) and \(v\) as diameter does not contain any points of \(P\) that are neighbors of \(u\) or \(v\) in \(G\). A locally Gabriel graph(LGG) is a generalization of Gabriel graph and is motivated by applications in wireless networks. Unlike a Gabriel graph, there is no unique LGG on a given point set since no edge in a LGG is necessarily included or excluded. Thus the edge set of the graph can be customized to optimize certain network parameters depending on the application. The unit distance graph(UDG), introduced by Erdos, is also a LGG. In this paper, we show the following combinatorial bounds on edge complexity and independent sets of LGG: (i) For any \(n\), there exists LGG with \(\Omega (n^{5/4})\) edges. This improves upon the previous best bound of \(\Omega (n^{1+\frac{1}{\log \log n}})\). (ii) For various subclasses of convex point sets, we show tight linear bounds on the maximum edge complexity of LGG. (iii) For any LGG on any \(n\) point set, there exists an independent set of size \(\Omega (\sqrt{n}\log n)\).     

The Generation of Maximal Triangle-Free Graphs

In this paper we present an efficient algorithm for generating maximal triangle-free graphs. A program based on this algorithm has been used to check a conjecture of Erdo´´s about the local density of triangle-free graphs and turned out to be very powerful for the computation of triangle Ramsey numbers.     

Maximal Rigid Objects as Noncrossing Bipartite Graphs

We classify the maximal rigid objects of the Σ² τ-orbit category ${\mathcal{C}}(Q)$ of the bounded derived category for the path algebra associated to a Dynkin quiver Q of type A, where τ denotes the Auslander-Reiten translation and Σ² denotes the square of the shift functor, in terms of bipartite noncrossing graphs (with loops) in a circle. We describe the endomorphism algebras of the maximal rigid objects, and we prove that a certain class of these algebras are iterated tilted algebras of type A.     

Minimally k-Edge-Connected Directed Graphs of Maximal Size

Let D=(V,E) be a minimally k-edge-connected simple directed graph. We prove that there is a function f(k) such that |V|f(k) implies |E|2k(|V|–k). We also determine the extremal graphs whose size attains this upper bound.Basic Research in Computer Science, funded by the Danish National Research Foundation.Supported by the MTA-ELTE Egerváry Research Group on Combinatorial Optimization, and the Hungarian Scientific Research Fund grant No. F034930, T037547, and FKFP grant No. 0143/2001. Part of this research was done when the second author visited BRICS, University of Aarhus, Denmark.     

Spectral Integral Variations of Degree Maximal Graphs

The concept of the spectral integral variation was introduced by Fan [Fan Yizheng (2002). On spectral integral variations of graphs. Linear and Multilinear Algebra , 50 , 133-142] to study the general graphs with all changed eigenvalues moving up by integers when an edge is added. Here we consider the spectral integral variations of maximal graphs G , and successfully give an equivalent condition for the spectral integral variation of G occurring in two places by adding an edge e . We also characterize whether the graph G + e is maximal so that an explicit interpretation of the above condition is obtained, where G + e denotes the graph obtained from G by adding an edge e .     

Finding All Maximal Cliques in Dynamic Graphs

Clustering applications dealing with perception based or biased data lead to models with non-disjunct clusters. There, objects to be clustered are allowed to belong to several clusters at the same time which results in a fuzzy clustering. It can be shown that this is equivalent to searching all maximal cliques in dynamic graphs like G _t = (V,E _t), where E _{t – 1} E _t, t = 1,...,T; E ₀ = . In this article algorithms are provided to track all maximal cliques in a fully dynamic graph.     

Spectral Integral Variations of Degree Maximal Graphs

The concept of the spectral integral variation was introduced by Fan [Fan Yizheng (2002). On spectral integral variations of graphs. Linear and Multilinear Algebra , 50 , 133-142] to study the general graphs with all changed eigenvalues moving up by integers when an edge is added. Here we consider the spectral integral variations of maximal graphs G , and successfully give an equivalent condition for the spectral integral variation of G occurring in two places by adding an edge e . We also characterize whether the graph G + e is maximal so that an explicit interpretation of the above condition is obtained, where G + e denotes the graph obtained from G by adding an edge e .     

Rare Events in Random Geometric Graphs

This work introduces and compares approaches for estimating rare-event probabilities related to the number of edges in the random geometric graph on a Poisson point process. In the one-dimensional setting, we derive closed-form expressions for a variety of conditional probabilities related to the number of edges in the random geometric graph and develop conditional Monte Carlo algorithms for estimating rare-event probabilities on this basis. We prove rigorously a reduction in variance when compared to the crude Monte Carlo estimators and illustrate the magnitude of the improvements in a simulation study. In higher dimensions, we use conditional Monte Carlo to remove the fluctuations in the estimator coming from the randomness in the Poisson number of nodes. Finally, building on conceptual insights from large-deviations theory, we illustrate that importance sampling using a Gibbsian point process can further substantially reduce the estimation variance.