Search

Consider the 2n (or O(n²)) min-cut problems on a graph with n nodes and nonnegative edge weights. Gomory and Hu [J. Soc. Indust. Appl. Math., 9 (1961), pp. 551–570] showed (essentially) that there are at most n-1 different min-cuts. They also described a compact structure (the flow equivalent tree) of size O(n) with the following property: for any pair of nodes, the value of a min-cut can be obtained from this structure. Furthermore, they showed how this structure can be found by solving only n - 1 min-cut problems. This paper contains generalizations of these results. For example, consider a k-terminal cut problem on a graph: for a given set of k nodes, delete a minimum weight set of edges (called a k-cut) so that each of the k nodes is in a different component. There are kn (or O(nk)) such problems. Hassin [Math. Oper. Res., 13 (1988), pp. 535–542] showed (essentially) that there are at most k-1n-1 (or O(nk-1)) different min k-cuts. We describe a compact structure of size O(nk-1) with the following property: for any k nodes, the value of a min k-cut can be obtained from this structure. We also show how this structure can be found by solving only k-1n-1 k-terminal cut problems. This work builds upon the results of Hassin [Math. Oper. Res., 13 (1988), pp. 535–542], [Oper. Res. Lett., 9 (1990), pp. 315–318], and [Lecture Notes in Comput. Sci. 450, 1990, pp. 228–299]. [ABSTRACT FROM AUTHOR]

In this paper we describe new constructions for de Bruijn sequences and Perfect Factors. These constructions are all based upon the idea of constructing one sequence (or set of sequences) from another. As a result of this fact, the sequences obtained from these construction methods possess simple decoding algorithms based on decoding the sequences used to construct them. Such decoding algorithms are of importance in position-location applications. [ABSTRACT FROM AUTHOR]

An old problem raised independently by Jacobson and Schönheim seeks to determine the maximum for which every graph with edges contains a pair of edge-disjoint isomorphic subgraphs with s edges. In this paper we determine this maximum up to a constant factor. We show that every m-edge graph contains a pair of edge-disjoint isomorphic subgraphs with at least c(m log m)2/3 edges for some absolute constant c, and find graphs where this estimate is off only by a multiplicative constant. Our results improve bounds of Erdös, Pach, and Pyber from 1987. [ABSTRACT FROM AUTHOR]

A graph G is called (r, s)-edge-choosable if for every assignment of sets of size r to the edges of G it is possible to choose for every edge an s-element subset from its set such that the subsets chosen for any pair of adjacent edges are disjoint. The list fractional chromatic index of a graph G is the infimum of all numbers r/s for which G is (r, s)-edge-choosable. Mohar [http://www.fmf.uni-lj.si/~mohar/(June 2003)] posed a problem asking whether every cubic graph is (7,2)-edge-choosable. In 2009, Cranston and West [SIAM J. Discrete Math., 23 (2009), pp. 872-881] showed that every 3-edge-colorable cubic graph is (7,2)-edge-choosable and gave a sufficient condition with the help of which they proved that many non-3-edge-colorable-cubic graphs are (7,2)-edge-choosable. In this paper we prove that every bridgeless cubic graph is (7,2)-edge-choosable. We show that this result cannot be improved in the family of all cubic graphs, in the sense that there exists a cubic graph with list fractional chromatic index 7/2. The original question of Mohar remains open, and we further pose several related problems. [ABSTRACT FROM AUTHOR]

The first-fit chromatic number of a graph is the number of colors needed in the worst case of a greedy coloring. It is also called the Grundy number, which is defined to be the maximum number of classes in an ordered partition of the vertex set of a graph G into independent sets V1, V2, … , Vk so that for each 1 ≤ i < j ≤ k and for each x ϵ Vi there exists a y ϵ Vi such that x and y are adjacent. In this paper, we study the first-fit chromatic number of outerplanar and planar graphs as well as Cartesian products of graphs, and in particular we give asymptotically tight results for outerplanar graphs. [ABSTRACT FROM AUTHOR]

Recently, D. Corneil found a simple 3-sweep lexicographic breadth first search (LexBFS) algorithm for the recognition of proper interval graphs. We point out how to modify Corneil's algorithm to make it a certifying algorithm, and then describe a similar certifying 3-sweep LexBFS algorithm for the recognition of proper interval bigraphs. It follows from an earlier paper that the class of proper interval bigraphs is equal to the better known class of bipartite permutation graphs, and so we have a certifying algorithm for that class as well. All our algorithms run in time O(m+n), including the certification phase. The certificates of representability (the intervals) can be authenticated in time O(m + n). The certificates of nonrepresentability (the forbidden subgraphs) can be authenticated in time O(n). [ABSTRACT FROM AUTHOR]

Splitting off two edges su, sv in a graph G means deleting su, sv and adding a new edge uv. Let G = (V + s, E) be k-edge-connected in V (k ≥ 2) and let d(s) be even. Lovász proved that the edges incident to s can be split off in pairs in a such a way that the resulting graph on vertex set V is k-edge-connected. In this paper we investigate the existence of such complete splitting sequences when the set of split edges has to meet additional requirements. We prove structural properties of the set of those pairs u, v of neighbors of s for which splitting off su, sv destroys k-edge-connectivity. This leads to a new method for solving problems of this type. By applying this method we obtain a short proof for a recent result of Nagamochi and Eades on planarity-preserving complete splitting sequences and prove the following new results: let G and H be two graphs on the same set V + s of vertices and suppose that their sets of edges incident to s coincide. Let G (H) be k-edge-connected (l-edge-connected, respectively) in V (k, l ≥ 2) and let d(s) be even. Then there exists a pair su, sv which can be split off in both graphs preserving k-edge-connectivity in G (l-edge-connectivity in H, respectively), provided d(s) ≥ 6. If k and l are both even, then such a pair always exists. By using these edge-splitting results and the polymatroid intersection theorem we give a polynomial algorithm for the problem of simultaneously augmenting the edge-connectivity of two graphs by adding a (common) set of new edges of (almost) minimum size. [ABSTRACT FROM AUTHOR]

Let G be a 3-connected plane graph. Plummer and Toft [J. Graph Theory, 11 (1987), pp. 507–515] conjectured that χc(G) ≤ Δ&ast;(G) + 2, where χc(G) is the cyclic chromatic number of G and Δ&ast;(G) the maximum face size of G. Horňák and Jendrol' [J. Graph Theory, 30 (1999), pp. 177–189] and Borodin and Woodall [SIAM J. Discrete Math., submitted] independently proved this conjecture when Δ&ast;(G) is large enough. Moreover, Borodin and Woodall proved a stronger statement that χc(G) ≤ Δ&ast;(G) + 1 holds if Δ&ast;(G) ≥ 122. In this paper, we prove that χc(G) ≤ Δ&ast;(G) + 1 holds if Δ&ast;(G) ≥ 60. [ABSTRACT FROM AUTHOR]

A tree, being a connected acyclic graph, can be bicolored in two ways, which differ from each other by exchange of the colors. We shall say that a tree is equicolorable if these bicolorings assign the two colors to equal numbers of vertices. Labelled equicolored trees have been enumerated several times in the literature, and from this result it is easy to enumerate labelled equicolorable trees. The result is that the probability that a randomly chosen n-vertex labelled tree is equicolorable is asymptotically just twice the probability that its vertices would be equicolored if they were assigned colors by independent unbiased coin flips. Our goal in this paper is the enumeration of unlabelled equicolorable trees (that is, trees up to isomorphism), both exactly (in terms of generating functions) and asymptotically. We treat both the rooted and unrooted versions of this problem and conclude that in either case the probability that a randomly chosen n-vertex unlabelled tree is equicolorable is asymptotically 1.40499… times as large as the probability that it would be equicolored if its vertices were assigned colors by independent unbiased coin flips. [ABSTRACT FROM AUTHOR]

In this paper we consider procedures for completely disconnecting a complete graph on n vertices Kn. By this we simply mean that we wish to remove all of the edges of Kn in a sequence of steps by which the graph Kn is successively transformed into the empty graph on n vertices. The rules are that, on each step, we may remove at most one edge from each connected component of the present graph, and in addition we may impose a limit w on the maximum number of edges we can remove at a time. What is the minimum number of steps fw (n) it will take to completely disconnect Kn? The two cases considered are w = ∞ and w = 2. We show that the ratio of fw(n) to the number of edges of Kn is asymptotic to 2/3 in the first case and to 1/2 + λ(1 - λ) = .74194412 … in the second, where λ is the real root of the equation λ = 2(1 - λ)³. [ABSTRACT FROM AUTHOR]

The following constrained matching problem arises in the area of manpower scheduling. Consider an undirected graph G = (V, E) and a digraph D = (V, A). A master/slave-matching (MS-matching) in G with respect to D is a matching in G such that for each arc (u,v) ∈ A for which the node u is matched, the node v is matched too. The problem is to find an MS-matching of maximum cardinality. This paper addresses the special case where G is bipartite with bipartition V = W ∪ U and every (weakly) connected component of D is either an isolated node or two nodes in U which are joined by a single arc. The polyhedral structure of this special case is investigated and a min-max theorem which characterizes the cardinality of a maximum MS-matching in terms of the weight of a special node cover is derived. This min-max theorem includes as a special case the theorem of König. [ABSTRACT FROM AUTHOR]

We shall define the k-isoperimetric connectivity Ak of a regular graph F as the minimum number of arcs originating in a set with cardinality not exceeding half the order of the graph and containing at least k vertices. Clearly λk ≤ dk - ek, where d is the degree of Γ and ek is the maximal number of edges induced on a set of k vertices. We shall show that Cayley graphs with a prime order and arc-transitive graphs have λk = dk-ek, provided that d ≥ 3k - 3. We describe all vertex-transitive graphs where λ2 ≤ 2d - 3. [ABSTRACT FROM AUTHOR]

There is a polynomial algorithm which finds a decomposition of any given 4-regular graph into two triangle-free 2-factors or shows that such a decomposition does not exist. [ABSTRACT FROM AUTHOR]

If H is a 3-graph, then ex(n;H) denotes the maximum number of edges in a 3-graph on n vertices containing no sub-3-graph isomorphic to H. Let S(n) denote the 3-graph on n vertices obtained by partitioning the vertex set into parts of sizes [n/2] and [n/2] and taking as edges all triples that intersect both parts. Let s(n) denote the number of edges in S(n). Let F(3, 3) denote the 3-graph {123, 145, 146, 156, 245, 246, 256, 345, 346, 356}.We prove that if n ≠5, then ex(n; F(3, 3)) = s(n), and that the unique optimal 3-graph is S(n). [ABSTRACT FROM AUTHOR]

Let L(G) denote the set of all odd cycle lengths of a graph G. Gyárfás gave an upper bound for χ(G) depending on the size of this set: if |L(G)| = k ≥ 1, then χ(G) ≤ 2k + 1 unless some block of G is a K2k+2, in which case χ(G) = 2k + 2. This bound is generally tight, but when investigating L(G) of special forms, better results can be obtained. Wang completely analyzed the case L(G) = {3, 5} Camacho proved that if L(G) = {k, k + 2}, k ≥ 5, then χ(G) ≤ 4. We show that L(G) = {5, 7} implies χ(G) = 3. [ABSTRACT FROM AUTHOR]

Let F be a family of graphs. Two graphs G1 = (V1,E1),G2 = (V2,E2) are said to have the same F-structure if there is a bijection f : V1→V2 such that a subset S induces a graph belonging to F in G1 if and only if its image f(S) induces a graph belonging to F in G2. We characterize those graphs which have the same {P3, P3}-structure, or the same {K3,K3}-structure. This characterization shows that graph H is perfect if and only if it has the {P3, P3}-structure of some perfect graph G. In proving the main result, we need and prove the following result, which is of independent interest: If a graph J is claw-free and co-claw-free, then either (i) J has at most nine vertices, or (ii) every component of J is a path or a hole, or (iii) every component of J is a path or a hole. [ABSTRACT FROM AUTHOR]

The detachment of vertex is the inverse operation of merging vertices s1,..., st into s. We speak about {d1,..., dt}-detachment if, for the detached graph G', the new degrees are specified as dG' (s1) = d1,..., dG'(st) = dt. We call a detachment k feasible if dG' (X) ≥ k whenever X separates two vertices of V (G) - s. In our main theorem, we give a necessary and sufficient condition for the existence of a k-feasible {d1,..., dt}-detachment of vertex s. This theorem also holds for graphs containing 3-vertex hyperedges disjoint from s. From special cases of the theorem, we get a characterization of those graphs whose edge connectivity can be augmented to k by adding γ edges and ρ 3-vertex hyperedges. We give a new proof for the theorem of Nash-Williams that characterizes the existence of a simultaneous detachment of the vertices of a given graph such that the resulting graph is k-edge-connected. [ABSTRACT FROM AUTHOR]

The bar visibility number of a graph G, denoted b(G), is the minimum t such that G can be represented by assigning each vertex x the set Sx of points in at most t horizontal segments in the plane so that uv ∈ E(G) if and only if some point of Su sees some point of Sv via a vertical segment of positive width unobstructed by assigned points. Among our results are the following: (1) Every planar graph has bar visibility number at most 2, which is sharp. (2)r ≤ b(Km,n) ≤ r + 1, where r = [mn+4/2m+2n]. (3) b(Kn) = [n/6]. (4) If G has n vertices, then b(G) ≤ [n/6] + 2. [ABSTRACT FROM AUTHOR]

We characterize the switching classes that do not contain an acyclic graph. The characterization is by means of a set of forbidden induced subgraphs. We prove that in addition to switches of the cycles Cn for n &ges; 7, there are only finitely many such graphs in 24 switching classes, all having at most 9 vertices. `We give a representative of each of the 24 switching classes. [ABSTRACT FROM AUTHOR]

Studies the equitable coloring of k-uniform hypergraphs. Characteristics of a strong r-coloring; Double application of the nonsymmetric version of the Lovasz local lemma.

We show that each graph not containing a bad subdivision of K4 as a subgraph is strongly t-perfect. Here a graph G = (V, E) is strongly t-perfect if, for each weight function w : V → Z+, the maximum weight of a stable set is equal to the minimum (total) cost of a family of vertices, edges, and circuits covering any vertex v at least w(v) times. By definition, the cost of a vertex or edge is 1, and the cost of a circuit C is [&frac12&&verbar;VC&verbar;]. A subdivision of K4 is called bad if each triangle has become an odd circuit and if it is not obtained by making the edges in a 4-circuit of K4 evenly subdivided, while the other two edges are not subdivided. The theorem generalizes earlier results of Gerards [J. Combin. Theory Ser. B, 47 (1989), pp. 330- 348] on the strong t-perfection of odd-K4-free graphs and of Gerards and Shepherd [SIAM J. Discrete Math., 11 (1998), pp. 524-545] on the t-perfection of bad-K4-free graphs. [ABSTRACT FROM AUTHOR]

For integers j ≥ k, an L(j,k)-labeling of a graph G is an integer labeling of the vertices in V (G) such that adjacent vertices receive integers which differ by at least j, and vertices which are distance two apart receive labels which differ by at least k. We determine λkj(Kn × Km) for all j,k,m,n, and λ1²(Kpqr) for 3 ≤ q < p, p prime. [ABSTRACT FROM AUTHOR]

Given a graph G and an orientation σ of some of its edges, consider the graph AOσ(G) which is defined as follows: The vertices are the acyclic orientations of G which agree with σ, and two of these are adjacent if they differ only by the reversal of a single edge. AOσ(G) is easily seen to be bipartite. The purpose of this note is to show that it need not contain a Hamilton path even if both partite sets have the same cardinality. This answers a question of C. D. Savage [SIAM Rev., 39 (1997), pp. 605–629] and sheds new light onto two well-known open questions in the field of combinatorial Gray codes. [ABSTRACT FROM AUTHOR]

In this note we show a new upperbound for the function ex(n;TKp), i.e., the maximum number of edges of a graph of order n not containing a subgraph homeomorphic to the complete graph of order p. Further, for [2n+5&frac3;] ≤ p < n we provide exact values for this function. [ABSTRACT FROM AUTHOR]

A graph is a split graph if its vertices can be partitioned into a clique and a stable set. A graph is a k-split graph if its vertices can be partitioned into k sets, each of which induces a split graph. We show that the strong perfect graph conjecture is true for 2-split graphs and we design a polynomial algorithm to recognize a perfect 2-split graph. [ABSTRACT FROM AUTHOR]

We show that the size of the smallest depth-two N-superconcentrator is Θ(N log² N/log log N). Before this work, optimal bounds were known for all depths except two. For the upper bound, we build superconcentrators by putting together a small number of disperser graphs; these disperser graphs are obtained using a probabilistic argument. For obtaining lower bounds, we present two different methods. First, we show that superconcentrators contain several disjoint disperser graphs. When combined with the lower bound for disperser graphs of Kovari, Sós, and Turán, this gives an almost optimal lower bound of Ω(N(log N/log log N)²) on the size of N-superconcentrators. The second method, based on the work of Hansel, gives the optimal lower bound. The method of Kovari, Sós, and Turin can be extended to give tight lower bounds for extractors, in terms of both the number of truly random bits needed to extract one additional bit and the unavoidable entropy loss in the system. If the input is an n-bit source with min-entropy k and the output is required to be within a distance of ∈ from uniform distribution, then to extract even one additional bit, one must invest at least log(n - k) + 2 log(1/∈) - O(1) truly random bits; to obtain m output bits one must invest at least m - k + 2 log(1/∈) - O(1). Thus, there is a loss of 2 log(1/∈) bits during the extraction. Interestingly, in the case of dispersers this loss in entropy is only about log log(1/∈). [ABSTRACT FROM AUTHOR]

We establish that every cyclically 4-connected cubic planar graph of order at most 40 is hamiltonian. Furthermore, this bound is determined to be sharp, and we present all nonhamiltonian examples of order 42. In addition we list all nonhamiltonian cyclically 5-connected cubic planar graphs of order at most 52 and all nonhamiltonian 3-connected cubic planar graphs of girth 5 on at most 46 vertices. The fact that all 3-connected cubic planar graphs on at most 176 vertices and with face size at most 6 are hamiltonian is also verified. [ABSTRACT FROM AUTHOR]

We describe efficient algorithms for finding even cycles in undirected graphs. Our main results are the following: (i) For every k ≥ 2, there is an O(V²) time algorithm that decides whether an undirected graph G = (V,E) contains a simple cycle of length 2k, and finds one if it does. (ii) There is an O(V²) time algorithm that finds a shortest even cycle in an undirected graph G = (V, E). [ABSTRACT FROM AUTHOR]