Search

Abstract: The separation dimension π ( G ) of a hypergraph G is the smallest natural number k for which the vertices of G can be embedded in R k so that any pair of disjoint edges in G can be separated by a hyperplane normal to one of the axes. Equivalently, it is the cardinality of a smallest family F of total orders of V ( G ), such that for any two disjoint edges of G, there exists at least one total order in F in which all the vertices in one edge precede those in the other. Separation dimension is a monotone parameter; adding more edges cannot reduce the separation dimension of a hypergraph. In this article, we discuss the influence of separation dimension and edge‐density of a graph on one another. On one hand, we show that the maximum separation dimension of a k‐degenerate graph on n vertices is O ( k lg lg n ) and that there exists a family of 2‐degenerate graphs with separation dimension Ω ( lg lg n ). On the other hand, we show that graphs with bounded separation dimension cannot be very dense. Quantitatively, we prove that n‐vertex graphs with separation dimension s have at most 3 ( 4 lg n ) s − 2 · n edges. We do not believe that this bound is optimal and give a question and a remark on the optimal bound. [ABSTRACT FROM AUTHOR]

The separation dimension of a graph G is the smallest natural number k for which the vertices of G can be embedded in ℝk such that any pair of disjoint edges in G can be separated by a hyperplane normal to one of the axes. Equivalently, it is the smallest possible cardinality of a family Ƒ of total orders of the vertices of G such that for any two disjoint edges of G, there exists at least one total order in Ƒ in which all the vertices in one edge precede those in the other. In general, the maximum separation dimension of a graph on n vertices is Θ(log n). In this article, we focus on bounded degree graphs and show that the separation dimension of a graph with maximum degree d is at most 29 log*dd. We also demonstrate that the above bound is nearly tight by showing that, for every d, almost all d-regular graphs have separation dimension at least _d/2_. [ABSTRACT FROM AUTHOR]

We show that every graph of maximum degree 3 can be represented as the intersection graph of axis parallel boxes in three dimensions, that is, every vertex can be mapped to an axis parallel box such that two boxes intersect if and only if their corresponding vertices are adjacent. In fact, we construct a representation in which any two intersecting boxes touch just at their boundaries. [ABSTRACT FROM AUTHOR]

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a′( G). It was conjectured by Alon, Sudakov and Zaks (and much earlier by Fiamcik) that a′( G) ⩽ Δ + 2, where Δ = Δ( G) denotes the maximum degree of the graph. If every induced subgraph H of G satisfies the condition | E( H)| ⩽ 2| V( H)|−1, we say that the graph G satisfies Property A. In this article, we prove that if G satisfies Property A, then a′( G) ⩽ Δ + 3. Triangle-free planar graphs satisfy Property A. We infer that a′( G) ⩽ Δ + 3, if G is a triangle-free planar graph. Another class of graph which satisfies Property A is 2-fold graphs (union of two forests). © 2011 Wiley Periodicals, Inc. J Graph Theory [ABSTRACT FROM AUTHOR]

Contraction of an edge e merges its end points into a new single vertex, and each neighbor of one of the end points of e is a neighbor of the new vertex. An edge in a k-connected graph is contractible if its contraction does not result in a graph with lesser connectivity; otherwise the edge is called non-contractible. In this paper, we present results on the structure of contractible edges in k-trees and k-connected partial k-trees. Firstly, we show that an edge e in a k-tree is contractible if and only if e belongs to exactly one ( k + 1) clique. We use this characterization to show that the graph formed by contractible edges is a 2-connected graph. We also show that there are at least | V( G)| + k − 2 contractible edges in a k-tree. Secondly, we show that if an edge e in a partial k-tree is contractible then e is contractible in any k-tree which contains the partial k-tree as an edge subgraph. We also construct a class of contraction critical 2 k-connected partial 2 k-trees. [ABSTRACT FROM AUTHOR]

A k-cube (or “a unit cube in k dimensions”) is defined as the Cartesian product $$R_1 \times \cdots \times R_k$$ where R i (for 1 ≤ i ≤ k) is an interval of the form [ a i, a i + 1] on the real line. The k-cube representation of a graph G is a mapping of the vertices of G to k-cubes such that the k-cubes corresponding to two vertices in G have a non-empty intersection if and only if the vertices are adjacent. The cubicity of a graph G, denoted as cub( G), is defined as the minimum dimension k such that G has a k-cube representation. An interval graph is a graph that can be represented as the intersection of intervals on the real line - i.e., the vertices of an interval graph can be mapped to intervals on the real line such that two vertices are adjacent if and only if their corresponding intervals overlap. We show that for any interval graph G with maximum degree Δ, $${\rm cub} (G) \leq\lceil\log_2 \Delta\rceil +4$$. This upper bound is shown to be tight up to an additive constant of 4 by demonstrating interval graphs for which cubicity is equal to $$\lceil\log_2 \Delta\rceil$$. [ABSTRACT FROM AUTHOR]

The Hadwiger number η( G) of a graph G is the largest integer n for which the complete graph K n on n vertices is a minor of G. Hadwiger conjectured that for every graph G, η( G) ≥ χ( G), where χ( G) is the chromatic number of G. In this paper, we study the Hadwiger number of the Cartesian product $$G \square H$$ of graphs. As the main result of this paper, we prove that $$\eta (G_1 \square G_2) \ge h\sqrt{l}\left (1 - o(1) \right )$$ for any two graphs G 1 and G 2 with η( G 1) = h and η( G 2) = l. We show that the above lower bound is asymptotically best possible when h ≥ l. This asymptotically settles a question of Z. Miller (1978). As consequences of our main result, we show the following: [ABSTRACT FROM AUTHOR]

We relate the number of minimum cuts in a weighted undirected graph with various structural parameters of the graph. In particular, we provide upper bounds for the number of minimum cuts in terms of the radius, diameter, minimum degree, maximum degree, chordality, girth, and some other parameters of the graph. [ABSTRACT FROM AUTHOR]

We give a deterministic algorithm that constructs a graph of girth log[SUBk] (n) + O(1) and minimum degree k - 1, taking number of nodes n and number of edges e = [nk/2] (where k < &fracn3;) as input. The degree of each node is guaranteed to be k - 1, k, or k + 1, where k is the verage degree. Although constructions that achieve higher values of girth -- up to &frac43; log[SUBk -1] (n) - with the same number of edges are known, the proof of our construction uses only very simple counting arguments in comparison. Our method is very simple and perhaps the most intuitive: We start with an initially empty graph and keep introducing edges one by one, connecting vertices which are at large distances in the current graph. In comparison with the Erdös -- Sachs proof, ours is slightly simpler while the value it achieves is slightly lower. Also, our algorithm works for all values of n and k < &fracn3;, unlike most of the earlier constructions. [ABSTRACT FROM AUTHOR]