Search
Search Results
-
On Bounding the Diameter of a Distance-Regular Graph
In this note we investigate how to use an initial portion of the intersection array of a distance-regular graph to give an upper bound for the...
-
Even Maps, the Colin de Verdière Number and Representations of Graphs
Van der Holst and Pendavingh introduced a graph parameter σ , which coincides with the more famous Colin de Verdière graph parameter μ for small...
-
Properties of π-skew Graphs with Applications
The skewness of a graph G , denoted by sk ( G ), is the minimum number of edges in G whose removal results in a planar graph. It is an important...
-
On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic
Given a set of n points in ℝ d , the (monochromatic) Closest Pair problem asks to find a pair of distinct points in the set that are closest in the ℓ p -m...
-
Generically Globally Rigid Graphs Have Generic Universally Rigid Frameworks
We show that any graph that is generically globally rigid in ℝ d has a realization in ℝ d that is both generic and universally rigid. This also implies...
-
On the Size of K-Cross-Free Families
Two subsets A , B of an n -element ground set X are said to be crossing , if none of the four sets A ∩ B , A \ B , B \ A and X \( A ∪ B ) are empty. It was...
-
Two recursive inequalities for crossing numbers of graphs
In this paper, two recursive inequalities for crossing numbers of graphs are given by using basic counting method. As their applications, the...
-
An Introduction to Coding Sequences of Graphs
In this paper, we introduce a new representation of simple undirected graphs in terms of set of vectors in finite dimensional vector spaces over...
-
On-Line Approach to Off-Line Coloring Problems on Graphs with Geometric Representations
The main goal of this paper is to formalize and explore a connection between chromatic properties of graphs with geometric representations and...
-
Representation of finite graphs as difference graphs of S-units. II
In Part I of the present paper the following problem was investigated. Let G be a finite simple graph, and S be a finite set of primes. We say that G ...
-
Drawing complete multipartite graphs on the plane with restrictions on crossings
A graph is 1-planar if it can be drawn on a plane so that each edge is crossed by at most one other edge. A plane graph with near independent...
-
Joins of 1-planar graphs
A graph is called 1-planar if it admits a drawing in the plane such that each edge is crossed at most once. In this paper, we study 1-planar graph...
-
Core-free, rank two coset geometries from edge-transitive bipartite graphs
It is known that the Levi graph of any rank two coset geometry is an edge-transitive graph, and thus coset geometries can be used to construct many...
-
Lower bounds for boxicity
An axis-parallel b -dimensional box is a Cartesian product R 1 ×– 2 ×...× R b where R i is a closed interval of the form [ a i ; b i ] on the real line. For...
-
The Rectilinear Crossing Number of K n : Closing in (or Are We?)
The calculation of the rectilinear crossing number of complete graphs is an important open problem in combinatorial geometry, with important and...
-
Representing Graphs in Steiner Triple Systems
Let G = ( V , E ) be a simple graph and let T = ( P , B ) be a Steiner triple system. Let φ be a one-to-one function from V to P . Any edge e = { u , v } has...
-
Rectangle and Square Representations of Planar Graphs
In the first part of this survey, we consider planar graphs that can be represented by a dissections of a rectangle into rectangles. In rectangular...
-
Complexity of the Positive Semidefinite Matrix Completion Problem with a Rank Constraint
We consider the decision problem asking whether a partial rational symmetric matrix with an all-ones diagonal can be completed to a full positive...