Search

Let gd(n) be the set of d-regular simple graphs with n vertices, and for G = (V, E) in gd(n) let f : → {1, 2, . . . , n} be a objective coloring of the vertices of G. Also let α denote an interference parameter in {0, 1,. . . ,n - 1}, and define the interference number of f with respect to G and α as the number of edges {u, v} in E for which min{/f(u) - f(v)\,n - f(u) - f(v)\} < α. We consider two interference number problems for feasible (n, α, d). The first is to specify a G E and an f for which the interference number is as small as possible. The second is to determine a G &epsiv; gd(n) whose minimum interference number over all f is as large as possible. A previous paper completely solves both problems for d = 2. The present paper solves the first problem for all d ≥ 3 and obtains partial results for the second problem for d ≥ 3 that focus on interference-minimizing f's when G consists of disjoint copies of Kd+1. [ABSTRACT FROM AUTHOR]

Given a directed graph G and an arc weight function w : E(G) → R+, the maximum directed cut problem (max dicut) is that of finding a directed cut δ(X) with maximum total weight. In this paper we consider a version of max dicut--max dicut with given sizes of parts or max dicut with gsp--whose instance is that of max dicut plus a positive integer p, and it is required to find a directed cut δ(X) having maximum weight over all cuts δ(X) with |X| = p. Our main result is a 0.5-approximation algorithm for solving the problem. The algorithm is based on a tricky application of the pipage rounding technique developed in some earlier papers by two of the authors and a remarkable structural property of basic solutions to a linear relaxation. The property is that each component of any basic solution is an element of a set {0,δ, 1/2, 1 - δ, 1}, where δ is a constant that satisfies 0 < δ < 1/2 and is the same for all components. [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]

In the (k, λ)-subgraph problem, we are given an undirected graph G = (V, E) with edge costs and two positive integers k and λ, and the goal is to find a minimum cost simple λ-edge-connected subgraph of G with at least k nodes. This generalizes several classical problems, such as the minimum cost k-spanning tree problem, or k-MST (which is a (k, 1)-subgraph), and the minimum cost λ-edge-connected spanning subgraph (which is a (|V(G)|, λ-subgraph). The only previously known results on this problem [L. C. Lau, J. S. Naor, M. R. Salavatipour, and M. Singh, SIAM J. Comput., 39 (2009), pp. 1062-1087], [C. Chekuri and N. Korula, in Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Bangalore, India, LIPIcs 2, Schloss Dagstuhl--Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2008, pp. 119-130] show that the (k, 2)-subgraph problem has an O(log² n)-approximation (even for 2-node-connectivity) and that the (k, λ)-subgraph problem in general is almost as hard as the densest k-subgraph problem. In this paper we show that if the edge costs are metric (i.e., satisfy the triangle in equality), like in the k-MST problem, then there is an O(1)-approximation algorithm for the (k, λ)-subgraph problem. This essentially generalizes the k-MST constant factor approximability to higher connectivity. [ABSTRACT FROM AUTHOR]

For a real c = 1 and an integer n, let f(n, c) denote the maximum integer f such that every graph on n vertices contains an induced subgraph on at least f vertices in which the maximum degree is at most c times the minimum degree. Thus, in particular, every graph on n vertices contains a regular induced subgraph on at least f(n, 1) vertices. The problem of estimating f(n, 1) was posed long ago by Erdős, Fajtlowicz, and Staton. In this paper we obtain the following upper and lower bounds for the asymptotic behavior of f(n, c): (i) For fixed c > 2.1, n1-O(1/c) ≤ f(n, c) ≤ O(cn/log n). (ii) For fixed c = 1+ε with e > 0 sufficiently small, f(n, c) ≥ nΩ(ε²/ln(1/ε)). (iii) O(ln n) ≤ f(n, 1) ≤ O(n1/2 ln3/4 n). An analogous problem for not necessarily induced subgraphs is briefly considered as well. [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]

Asteroidal triple free (AT-free) graphs have been introduced as a generalization of interval graphs, since interval graphs are exactly the chordal AT-free graphs. While for interval graphs it is obvious that there is always a linear ordering of the vertices, such that for each triple of independent vertices the middle one intercepts any path between the remaining vertices of the triple, it is not clear that such an ordering exists for AT-free graphs in general. In this paper we study graphs that are defined by enforcing such an ordering. In particular, we introduce two subfamilies of AT-free graphs, namely, path orderable graphs and strong asteroid free graphs. Path orderable graphs are defined by a linear ordering of the vertices that is a natural generalization of the ordering that characterizes cocomparability graphs. On the other hand, motivation for the definition of strong asteroid free graphs comes from the fundamental work of Gallai on comparability graphs. We show that cocomparability graphs ⊂ path orderable graphs ⊂ strong asteroid free graphs ⊂ AT-free graphs. In addition, we settle the recognition question for the two new classes by proving that recognizing path orderable graphs is NP-complete, whereas the recognition problem for strong asteroid free graphs can be solved in polynomial time. [ABSTRACT FROM AUTHOR]

In 1955 Kotzig [A. Kotzig, Math. Slovaca, 5 (1955), pp. 111-113] proved that every planar 3-connected graph contains an edge such that the sum of degrees of its end-vertices is at most 13. Moreover, if the graph does not contain 3-vertices, then this sum is at most 11. Such an edge is called light. The well-known result of Steinitz [E. Steinitz, Enzykl. Math. Wiss., 3 (1922), pp. 1-139] that the 3-connected planar graphs are precisely the skeletons of 3-polytopes gives an additional trump to Kotzig's theorem. On the other hand, in 1961, Tutte [W. T. Tutte, Indag. Math., 23 (1961), pp. 441-455] proved that every 3-connected graph, distinct from K4, contains a contractible edge. In this paper, we strengthen Kotzig's theorem by showing that every 3-connected planar graph distinct from K4 contains an edge that is both light and contractible. A consequence is that every 3-polytope can be constructed from tetrahedron by a sequence of splittings of vertices of degree at most 11. [ABSTRACT FROM AUTHOR]

In a graph G, an odd hole is an induced odd cycle of length at least 5. A clique of G is a set of pairwise adjacent vertices. In this paper we consider the class Ck of graphs whose cliques have a size bounded by a constant k. Given a graph G in Ck, we show how to recognize in polynomial time whether G contains an odd hole. [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]

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]

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]

Let G be an undirected graph with a set of vertices V and a set of edges E. Given an integer r, we assign at most r labels (representing "resources") to each vertex. We say that such an assignment is an r-configuration if, for each label c, the vertices labeled by c form a dominating set for G. In this paper, we are interested in the maximum number, Dr(G), of labels that can be assigned to the vertices of graph G by an r-configuration. The decision problem "D1(G) ≥ K?" (known as the domatic number problem) is NP-complete. We first investigate Dr(G) for general graphs and establish bounds on Dr(G) in terms of D1(G) and the minimum vertex degree of G. We then discuss Dr(G) for d-regular graphs. We clearly have Dr(G) ≤ r(d + 1). We show that the problem of testing if Dr(G) = r(d + 1) is solvable in polynomial time for d-regular graphs with ∣V∣ = 2(d + 1), but is NP-complete for those with ∣V∣ = a(d + 1) for some integer a ≥ 3. Finally, we discuss cubic (i.e., 3-regular) graphs. It is easy to show 2r ≤ Dr(G) ≤ 4r for cubic graphs. We show that the decision problem for D1(G) = K is co-NP-complete for K = 2 and is NP-complete for K = 4. Although there are many cubic graphs G with D1(G) = 2, surprisingly, every cubic graph has a 2-configuration with five labels, i.e., D2(G) ≥ 5 and such a 2-configuration can be constructed in polynomial time. We use this fact to show Dr(G) ≥. ⌊5r/2⌋ in general. [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]

Several isomorphism classes of graph coverings of a graph G have been enumerated by many authors. An enumeration of the isomorphism classes of n-fold coverings of a graph G was done by Kwak and Lee [Canad. J. Math., XLII (1990), pp. 747-761] and independently by Hofmeister [Discrete Math., 98 (1991), pp. 437-444]. An enumeration of the isomorphism classes of connected n-fold coverings of a graph G was recently done by Kwak and Lee [J. Graph Theory, 23 (1996), pp. 105-109]. But the enumeration of the isomorphism classes of regular coverings of a graph G has been done for only a few cases. In fact, the isomorphism classes of A-coverings of G were enumerated when A is the cyclic group Zn, the dihedral group Dn(n: odd), and the direct sum of m copies of Zp. (See [Discrete Math., 143 (1995), pp. 87-97], [J. Graph Theory, 15 (1993), pp. 621-627], and [Discrete Math., 148 (1996), pp. 85-105]). In this paper, we discuss a method to enumerate the isomorphism classes of connected A-coverings of a graph G for any finite group A and derive some formulas for enumerating the isomorphism classes of regular n-fold coverings for any natural number n. In particular, we calculate the number of the isomorphism classes of A-coverings of G when A is a finite abelian group or the dihedral group Dn. Our method gives partial answers to the open problems 1 and 2 in [Discrete Math., 148 (1996), pp. 85-105] and also gives a formula to calculate the number of the subgroups of a given index of any finitely generated free abelian group. [ABSTRACT FROM AUTHOR]

Hofmeister introduced the notion of a concrete (resp., concrete regular) covering of a graph G and gave formulas for enumerating the isomorphism classes of concrete (resp., concrete regular) coverings of G [Ars Combin., 32 (1991), pp. 121-127; SIAM J. Discrete Math., 8 (1995), pp. 51-61]. In this paper, we show that the number of the isomorphism classes of n-fold concrete (resp., concrete regular) coverings of G is equal to that of the isomorphism classes of n-fold (resp., regular) coverings of a new graph, the join G + ∞ of G and an extra vertex ∞. As a consequence, we can enumerate the isomorphism classes of concrete (resp., concrete regular) coverings of a graph by using known formulas for enumerating the isomorphism classes of coverings (resp., regular coverings) of a graph. [ABSTRACT FROM AUTHOR]

The even discrete torus Tn(k1, …, kn) is the graph on (Z/k1Z) × … × (Z/knZ), where each ki is even and x = (x1, …, xn) is joined to y = (y1, …,yn) if for some i we have xi = yi ± 1 and xj = yj for all j ≠ i. The main aim of this paper is to describe an ordering on the even discrete torus whose initial segments give a best possible isoperimetric inequality. This extends the partial solution of Bollobás and Leader [SIAM J. Discrete Math., 3 (1990), pp. 32-37] to a problem posed by Wang and Wang [SIAM J. Appl. Math., 33 (1977), pp. 55-59]. [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]

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]