Search

A monotone drawing of a graph G is a straight-line drawing of G such that, for every pair of vertices u,w in G, there exists a path Puw in G that is monotone in some direction luw. (Namely, the order of the orthogonal projections of the vertices of Puw on luw is the same as the order in which they appear in Puw.) The problem of finding monotone drawings for trees has been studied in several recent papers. The main focus is to reduce the size of the drawing. Currently, the smallest drawing size is O(n log n) × O(n log n). In this paper, we present an algorithm for constructing monotone drawings of trees on a grid of size at most 12n × 12n. The smaller drawing size is achieved by a procedure that carefully assigns primitive vectors to the paths of the input tree T. We also show that there exists a tree T0 such that any monotone drawing of T0 must use a grid of size at least n/9 × n/9. So the size of our monotone drawings is asymptotically optimal. [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]

Given a graph G and an integer k, two players take turns coloring the vertices of G one by one using k colors so that neighboring vertices get different colors. The first player wins if at the end of the game all the vertices of G are colored. The game chromatic number χg(G) is the minimum k for which the first player has a winning strategy. The paper [T. Bohman, A. M. Frieze, and B. Sudakov, Random Structures Algorithms, 32 (2008), pp. 223-235] began the analysis of the asymptotic behavior of this parameter for a random graph Gn,p. This paper provides some further analysis for graphs with constant average degree, i.e., np = O(1), and for random regular graphs. We show that with high probability (w.h.p.) c1χ(Gn,p) ≤ (Gn,p) c2χ (Gn,p) for some absolute constants 1 < c1 < c2. We also prove that if Gn,3 denotes a random n-vertex cubic graph, then w.h.p. χg(Gn,3) = 4. [ABSTRACT FROM AUTHOR]

A book with k pages consists of a straight line (the spine) and k half-planes (the pages), such that the boundary of each page is the spine. If a graph is drawn on a book with k pages in such a way that the vertices lie on the spine, and each edge is contained in a page, the result is a k-page book drawing (or simply a k-page drawing). The k-page crossing number vk(G) of a graph G is the minimum number of crossings in a k-page drawing of G. In this paper we investigate the k-page crossing numbers of complete graphs. We use semidefinite programming techniques to give improved lower bounds on vk(Kn) for various values of k. We also use a maximum satisfiability reformulation to obtain a computer-aided calculation of the exact value of vk(Kn) for several values of k and n. Finally, we investigate the best construction known for drawing Kn in k pages, calculate the resulting number of crossings, and discuss this upper bound in light of the new results reported in this paper. [ABSTRACT FROM AUTHOR]

Let G be a graph with a threshold function ϑ : V(G) → ℕ such that 1 ≤ ϑ(v) ≤ dG(v) for every vertex v of G, where DG(V) is the degree of v in G. Suppose we are given a target set S ⊆ V(G). This paper considers the following repetitive process on G. At time step 0 the vertices of S are colored black and the other vertices are colored white. After that, at each time step t > 0, the colors of white vertices (if any) are updated according to the following rule. All white vertices v that have at least ϑ(v) black neighbors at the time step t - 1 are colored black, and the colors of the other vertices do not change. The process runs until no more white vertices can update colors from white to black. The following optimization problem is called TARGET SET SELECTION: Find a target set S of smallest possible size such that all vertices in G are black at the end of the process. Such an S is called an optimal target set for G under the threshold function 9. We are interested in finding an optimal target set for the well-known class of honeycomb networks under an important threshold function called a strict majority threshold, where ϑ(v) = [(dG (v) + l)/2] for each vertex v in G. In a graph G, a feedback vertex set is a subset S ⊆ V(G) such that the subgraph induced by V(G) \ S is cycle-free. In this paper we give exact value on the size of the optimal target set for various kinds of honeycomb networks under a strict majority threshold, and as a by-product we also provide a minimum feedback vertex set for different kinds of regular graphs in the class of honeycomb networks. [ABSTRACT FROM AUTHOR]

Let k = (k1, … kn) be a sequence of n integers. For an increasing monotone graph property P we say that a base graph G = ([n], E) is k-resilient with respect to P if for every subgraph H ⊆ G such that dH(i) ≤ ki for every 1 ≤ i ≤ n the graph G - H possesses P. This notion naturally extends the idea of the local resilience of graphs recently initiated by Sudakov and Vu. In this paper we study the k-resilience of a typical graph from G(n, p) with respect to the Hamiltonicity property, where we let p range over all values for which the base graph is expected to be Hamiltonian. Considering this generalized approach to the notion of resilience our main result implies several corollaries which improve on the best known bounds of Hamiltonicity related questions. For one, it implies that for every positive ε > 0 and large enough values of K, if p > K ln n/n, then with high probability the local resilience of G(n, p) with respect to being Hamiltonian is at least (1 - e)np/3, improving on the previous bound for this range of p. Another implication is a result on optimal packing of edge-disjoint Hamilton cycles in a random graph. We prove that if p ≤ 1.02 ln n/n, then with high probability a graph G sampled from G(n, p) contains [δ(G)/2] edge-disjoint Hamilton cycles, extending the previous range of p for which this was known to hold. [ABSTRACT FROM AUTHOR]

In this paper, we provide a complete characterization of undirected SC-Hamiltonian graphs that are not strongly Hamiltonian. This conclusively settles a conjecture by Kryński [Discrete Appl. Math., 55 (1994), pp. 87-89], which was later disproved by Kabadi and Punnen [Discrete Math., 271 (2003), pp. 129-139] with a counterexample. We show that the Kabadi-Punnen counterexample is the only class of graphs where Kryński's conjecture is false, thereby proving the conjecture for all other graphs. [ABSTRACT FROM AUTHOR]

The independence ratio i(G) of a graph G is the ratio of its independence number and the number of vertices. The ultimate categorical independence ratio of a graph G is defined as limk→∞ i(G×k), where G×k denotes the kth categorical power of G. This parameter was introduced by Brown, Nowakowski, and Rall, who asked about its value for complete multipartite graphs. In this paper we determine the ultimate categorical independence ratio of complete multipartite graphs. [ABSTRACT FROM AUTHOR]

The Directed Maximum Leaf Out-Branching problem is to find an out-branching (i.e., a rooted oriented spanning tree) in a given digraph with the maximum number of leaves. In this paper, we obtain two combinatorial results on the number of leaves in out-branchings. We show that (1) every strongly connected n-vertex digraph D with minimum in-degree at least 3 has an outbranching with at least (n/4)1/3 - 1 leaves; (2) if a strongly connected digraph D does not contain an out-branching with k leaves, then the pathwidth of its underlying graph UG(D) is O(k log k), and if the digraph is acyclic with a single vertex of in-degree zero, then the pathwidth is at most 4k. The last result implies that it can be decided in time 2O(k log2 k) · nO(1) whether a strongly connected digraph on n vertices has an out-branching with at least k leaves. On acyclic digraphs the running time of our algorithm is 2O(k log k) · nO(1). [ABSTRACT FROM AUTHOR]

Recently Alon and Shapira [Every monotone graph property is testable, New York, Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, ACM Press, 2005, pp. 128-137] have established that every monotone graph property is testable. They raised the question whether their results can be extended to hypergraphs. The aim of this paper is to address this problem. Based on the recent regularity lemma of Rödl and Schacht [Regular partitions of hypergraphs, Combin. Probab. Comput., to appear], we prove that any monotone property of 3-uniform hypergraphs is testable answering in part the question of Alon and Shapira. Our approach is similar to the one developed by Alon and Shapira for graphs. We believe that based on the general version of the hypergraph regularity lemma the proof presented in this article extends to κ-uniform hypergraphs. [ABSTRACT FROM AUTHOR]

This paper studies t-interleaving on two-dimensional tori. Interleaving has applications in distributed data storage and burst error correction, and is closely related to Lee metric codes. A t-interleaving of a graph is defined as a vertex coloring in which any connected subgraph of t or fewer vertices has a distinct color at every vertex. We say that a torus can be perfectly t-interleaved if its t-interleaving number (the minimum number of colors needed for a t-interleaving) meets the sphere-packing lower bound, [t²/2]. We show that a torus is perfectly t-interleavable if and only if its dimensions are both multiples of t²+1/2 (if t is odd) or t (if t is even). The next natural question is how much bigger the t-interleaving number is for those tori that are not perfectly t-interleavable, and the most important contribution of this paper is to find an optimal interleaving for all sufficiently large tori, proving that when a torus is large enough in both dimensions, its t-interleaving number is at most just one more than the sphere-packing lower bound. We also obtain bounds on t-interleaving numbers for the cases where one or both dimensions are not large, thus completing a general characterization of t-interleaving numbers for two-dimensional tori. Each of our upper bounds is accompanied by an efficient t-interleaving scheme that constructively achieves the bound. [ABSTRACT FROM AUTHOR]

Let Kn,n denote the complete bipartite graph with n vertices in each bipartition set and Kn,n - I denote Kn,n with a 1-factor removed. An m-cycle system of Kn,n - I is a collection T of m-cycles such that each edge of Kn,n - I is contained in a unique m-cycle of T. In this paper, it is proved that the necessary and sufficient conditions for the existence of an m-cycle system of Kn,n - I are n ≡ 1 (mod 2), m ≡ 0 (mod 2), 4 ≤ m ≤ 2n, and n(n - 1) ≡ m) [ABSTRACT FROM AUTHOR]

In this paper, we obtain three general reduction formulas to determine the orientable and nonorientable genera for complete tripartite graphs. As corollaries, we (1) reduce the determination of the orientable (nonorientable, respectively) genera of 75 percent (85 percent, respectively) of nonsymmetric (with respect to l, m, and n) Kl,m,n to that of Km,m,n, and (2) determine the orientable and nonorientable genera for several classes of complete tripartite graphs. [ABSTRACT FROM AUTHOR]

For several graph-theoretic parameters such as vertex cover and dominating set, it is known that if their sizes are bounded by k, then the treewidth of the graph is bounded by some function of k. This fact is used as the main tool for the design of several fixed-parameter algorithms on minor-closed graph classes such as planar graphs, single-crossing-minor-free graphs, and graphs of bounded genus. In this paper we examine whether similar bounds can be obtained for larger minor-closed graph classes and for general families of graph parameters, including all those for which such behavior has been reported so far. Given a graph parameter P, we say that a graph family F has the parameter-treewidth property for P if there is an increasing function t such that every graph G ∈ F has treewidth at most t(P(C)). We prove as our main result that, for a large family of graph parameters called contraction-bidimensional, a minor-closed graph family F has the parameter-treewidth property if F has bounded local treewidth. We also show "if and only if" for some graph parameters, and thus, this result is in some sense tight. In addition we show that, for a slightly smaller family of graph parameters called minor-bidimensional, all minor-closed graph families F, excluding some fixed graphs, have the parameter-treewidth property. The contraction-bidimensional parameters include many domination and covering graph parameters such as vertex cover, feedback vertex set, dominating set, edge-dominating set, and q-dominating set (for fixed q). We use our theorems to develop new fixed-parameter algorithms in these contexts. [ABSTRACT FROM AUTHOR]

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]

In this paper we show that many general lower bounds on the broadcasting and gossiping time are optimal. In particular, let b(G) be the broadcasting time of a network G under the basic one-port model. The only lower bound on b(G) holding for every n vertices graph G is max(log2 n,Diam(G)), but the log2 n factor cannot be achieved in bounded degree networks. In fact, let the parameter d be defined in undirected graphs as the maximum degree minus one and for directed graphs as the maximum out-degree. Then, in [SIAM J. Discrete Math., 1 (1998), pp. 531–540; SIAM J. Discrete Math., 5 (1992), pp. 10–24] it has been proved that, for any graph G of parameter [This symbol cannot be presented in ASCII format] , where ξ is the largest real number such that ξd - ξd-1 - ξd-2 - … - ξ - 1 = 0. Since then many papers have proposed constructions of bounded degree networks having a small broadcast time [Proceedings of the 2nd International Euro-Par Conference (EUROPAR), Lecture Notes in Comput. Sci. 1123, Springer-Verlag, New York, 1996, pp. 313–324; IEEE Trans. Comput., 33 (1984), pp. 190–194], but so far the optimality of [SIAM J. Discrete Math., 1 (1998), pp. 531–540; SIAM J. Discrete Math., 5 (1992), pp. 10–24] was still an open question. In this paper we prove that the above lower bound is tight, improving all the existing upper bounds by means of probabilistic methods. Namely, we show that for n arbitrarily large there exist families of n vertices graphs in which a uniformly drawn graph has broadcasting time as predicted by [SIAM J. Discrete Math., 1 (1998), pp. 531–540; SIAM J. Discrete Math., 5 (1992), pp. 10–24] with probability converging to 1. Moreover, we show that [SIAM J. Discrete Math., 1 (1998), pp. 531–540; SIAM J. Discrete Math., 5 (1992), pp. 10–24] is attained even in the case of gossiping and systolic gossiping in the full-duplex mode. Finally, new upper bounds on bounded-degree and systolic gossiping are also determined in the directed and half-duplex modes. While the systolic construction is tight and matches the lower bound of [Inform and Comput., to appear], we strongly conjecture that the bounded-degree result is optimal and that a corresponding matching lower bound is still to be proven. [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]

Alon, Balogh, Keevash, and Sudakov proved that the (k - 1)-partite Turán graph maximizes the number of distinct r-edge-colorings with no monochromatic Kk for all fixed k and r = 2, 3, among all n-vertex graphs. In this paper, we determine this function asymptotically for r = 2 among n-vertex graphs with a sublinear independence number. Somewhat surprisingly, unlike Alon, Balog, Keevash, and Sudakov's result, the extremal construction from Ramsey-Turán theory, as a natural candidate, does not maximize the number of distinct edge-colorings with no monochromatic cliques among all graphs with a sublinear independence number, even in the 2-colored case. In the second problem, we determine the maximum number of triangles asymptotically in an n-vertex Kk-free graph G with α(G) = o(n). The extremal graphs have a similar structure to the extremal graphs for the classical Ramsey-Turán problem, i.e., when the number of edges is maximized. [ABSTRACT FROM AUTHOR]

The size-Ramsey number RF of a graph F is the smallest integer m such that there exists a graph G on m edges with the property that any coloring of the edges of G with two colors yields a monochromatic copy of F. In this paper, first we focus on the size-Ramsey number of a path Pn on n vertices. In particular, we show that 5n/2 - 15/2 ≤ R()Pn ≤ 74n for n sufficiently large. (The upper bound uses expansion properties of random d-regular graphs.) This improves the previous lower bound, RPn ≥ (1 + √2)n - O(1), due to Bollobás, and the upper bound, R()Pn ≤ 91n, due to Letzter. Next we study long monochromatic paths in an edge-colored random graph G(n, p) with pn → ∞. Let α > 0 be an arbitrarily small constant. Recently, Letzter showed that asymptotically almost surely (a.a.s.) any 2-edge coloring of G(n, p) yields a monochromatic path of length (2/3-α)n, which is optimal. Extending this result, we show that a.a.s. any 3-edge coloring of G(n, p) yields a monochromatic path of length (1/2 α)n, which is also optimal. We also consider a related problem and show that for any r ≥ 2, a.a.s. any r-edge coloring of G(n, p) yields a monochromatic connected subgraph on (1/(r - 1) - α)n vertices, which is also tight. [ABSTRACT FROM AUTHOR]

In 2011, the second author conjectured that every line graph G satisfies χ(G) ≤ max {ω(G), 5Δ(G)+8/6}. This conjecture is best possible as shown by replacing each edge in a 5-cycle by k parallel edges and taking the line graph. In this paper we prove the conjecture. We also develop more general techniques and results that will likely be of independent interest, due to their use in attacking the Goldberg-Seymour Conjecture. [ABSTRACT FROM AUTHOR]

We prove that an Eulerian graph G admits a decomposition into k closed trails of odd length if and only if and it contains at least k pairwise edge-disjoint odd circuits and k ≅ ∣E(G)∣ (mod 2). We conjecture that a connected 2d-regular graph of odd order with d ≥ 1 admits a decomposition into d odd closed trails sharing a common vertex and verify the conjecture for d ≤ 3. The case d = 3 is crucial for determining the flow number of a signed Eulerian graph which is treated in a separate paper [E. Máčajová and M. Škoviera, SIAM J. Discrete Math., 31 (2017), pp. 1937-1952]. The proof of our conjecture for d = 3 is surprisingly difficult and calls for the use of signed graphs as a convenient technical tool. [ABSTRACT FROM AUTHOR]

In this paper we prove an asymptotic multipartite version of a well-known theorem of Kühn and Osthus by establishing, for any graph H with chromatic number r, the asymptotic multipartite minimum degree threshold which ensures that a large r-partite graph G admits a perfect H-tiling. We also give the threshold for an H-tiling covering all but a linear number of vertices of G, in a multipartite analogue of results of Komlós and of Shokoufandeh and Zhao. [ABSTRACT FROM AUTHOR]

Given a digraph G, much attention has focused on the maximum number ø(G) of fixed points in a Boolean network ƒ : {0, 1}n → {0, 1}n with G as interaction graph. In particular, a central problem in network coding consists in studying the optimality of the feedback bound ø(G) ≤ 2τ, where τ is the minimum size of a feedback vertex set of G. In this paper, we study the maximum number øm(G) of fixed points in a monotone Boolean network with interaction graph G. We establish new upper and lower bounds on øm(G) that depend on the cycle structure of G. In addition to τ, the involved parameters are the maximum number v of vertex-disjoint cycles, and the maximum number v* of vertex-disjoint cycles verifying some additional technical conditions. We improve the feedback bound 2τ by proving that øm(G) is at most the largest sublattice of {0, 1}τ without chain of size v + 2, and without another forbidden pattern described by two disjoint antichains of size v* + 1. Then, we prove two optimal lower bounds: øm(G) ≥ v +1 and øm(G) ≥ 2v*. As a consequence, we get the following characterization: øm(G) = 2τ if and only if v* = τ. As another consequence, we get that if c is the maximum length of a chordless cycle of G, then 2v/3c ≤ øm(G) ≤ 2cv. Finally, with the techniques introduced, we establish an upper bound on the number of fixed points of any Boolean network according to its signed interaction graph. [ABSTRACT FROM AUTHOR]

In the Subset Odd Cycle Transversal (Subset OCT) problem, the input is a graph G, a subset of vertices T and a positive integer k and the objective is to determine whether there exists a k-sized vertex subset that intersects every odd cycle containing a vertex from T. Clearly, Subset OCT is a generalization of the classic Odd Cycle Transversal problem where the objective is to determine whether there exists a k-sized vertex subset that intersects every odd cycle in the given graph. We remark that Subset OCT also generalizes the well known Multiway Cut problem, as well as a parity constrained variant, the Odd Multiway Cut problem. Recently, Kakimura, Kawarabayashi, and Kobayashi [Proceedings of SODA, 2012, pp. 1726{1736] proposed a fixed parameter tractable (FPT) algorithm for this problem that runs in time ƒ(k)mn³ using the theory of graph minors, where ƒ is some function, and n and m denote the number of vertices and edges in the graph. However, the dependence of this function on k is at least triple exponential. In this paper, we give the first FPT algorithm for this problem where the exponential dependence of the running time of the algorithm on k is polynomial. Our algorithm avoids the use of the theory of graph minors, is self contained, and runs in time 2O(k³ log k)mn² log² n, thus improving upon the algorithm of Kakimura and co-authors with respect to both the parameter as well as the input size. Our algorithm utilizes a recursive application of "generalized" important separators to reduce the subset version of this problem to the standard version of the problem. [ABSTRACT FROM AUTHOR]

During the last decade, a lot of progress has been made in the enumerative branch of topological graph theory. Enumeration formulas were developed for a large class of graph covering projections. The purpose of this paper is to count graph covering projections of graphs such that the corresponding covering space is a connected graph. The main tool of the enumeration is Pó1ya's theorem. [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]

Bollobás and Thomason showed that a multigraph of order n and size at least n+ c(c ≥ 1) contains a cycle of length at most 2(⌊n/c⌋ + 1) ⌈log2 2c⌋. We show in this paper that a multigraph (with no loop) of order n and minimum degree at least 5 contains a chorded cycle (a cycle with a chord) of length at most 300 log2 n. As an application of this result, we show that a graph of sufficiently large order with minimum degree at least 3k + 8 contains k vertex-disjoint chorded cycles of the same length, which is analogous to Verstraëte's result: A graph of sufficiently large order with minimum degree at least 2k contains k vertex-disjoint cycles of the same length. [ABSTRACT FROM AUTHOR]

Let H = (V,E) be a hypergraph with vertex set V and edge set E of order nH = ΙV Ι and size mH = ΙEΙ. The hypergraph H is k-uniform if every edge of H has size k. Two vertices in H are adjacent if they belong to a common edge in H. A transversal in H is a subset of vertices in H that has a nonempty intersection with every edge of H. A total transversal in H is a transversal T in H with the additional property that every vertex in T is adjacent to some other vertex of T. The total transversal number γt(H) of of H is the minimum cardinality of a total transversal in H. For k ≥ 2, let bk = H∈Hk γt(H)/(nH + mH), ), where Hk denotes the class of all k-uniform hypergraphs containing no isolated vertices or isolated edges or multiple edges. It is known that b2 = 2/5, b3 = 1/3, b4 ≤ 1/3, and b5 ≤ 2/7. In this paper, we show that b4 = 2/7 and b6 ≤ 1/4. Further, for k ≥ 7, we show that b7 ≤ 2/9. These results on total transversals have applications in total domination in hypergraphs. A total dominating set in H is a subset of vertices D ⊆ V such that every vertex in H is adjacent to some vertex in D. The total domination number γt(H) is the minimum cardinality of a total dominating set in H. The following relationship between the total transversal number and the total domination number of uniform hypergraphs is known: For k ≥ 3 and H ∈ Hk, we have γt(H) ≤ (max{ 2/k+1, bk-1}) x nH. As a consequence of our results on the total transversal number, for k ∈ {2, 3, 4, 5, 6, 7, 8} and a hypergraph H ∈ Hk, we have γt(H) ≤ 2nH /(k + 1). [ABSTRACT FROM AUTHOR]

The Multicut problem, given a graph G, a set of terminal pairs T = {(si, ti) Ι 1 ≤ i ≤ r}, and an integer p, asks whether one can find a cutset consisting of at most p nonterminal vertices that separates all the terminal pairs, i.e., after removing the cutset, ti is not reachable from si for each 1 ≤ i ≤ r. The fixed-parameter tractability of Multicut in undirected graphs, parameterized by the size of the cutset only, has been recently proved by Marx and Razgon [SIAM J. Comput., 43 (2014), pp. 355--388] and, independently, by Bousquet, Daligault, and Thomassé [Proceedings of STOC, ACM, 2011, pp. 459-468], after resisting attacks as a long-standing open problem. In this paper we prove that Multicut is fixed-parameter tractable on directed acyclic graphs when parameterized both by the size of the cutset and the number of terminal pairs. We complement this result by showing that this is implausible for parameterization by the size of the cutset only, as this version of the problem remains W[1]-hard. [ABSTRACT FROM AUTHOR]

Tutte observed that every nowhere-zero κ-flow on a plane graph gives rise to a κ-vertex-coloring of its dual, and vice versa. Thus nowhere-zero integer flow and graph coloring can be viewed as dual concepts. Jaeger further shows that if a graph G has a face-κ-colorable 2-cell embedding in some orientable surface, then it has a nowhere-zero κ-flow. However, if the surface is nonorientable, then a face-κ-coloring corresponds to a nowhere-zero κ-flow in a signed graph arising from G. Graphs embedded in orientable surfaces are therefore a special case that the corresponding signs are all positive. In this paper, we prove that if an 8-edge-connected signed graph admits a nowhere-zero integer flow, then it has a nowhere-zero 3-flow. Our result extends Thomassen's 3-flow theorem on 8-edge-connected graphs to the family of all 8-edge-connected signed graphs. And it also improves Zhu's 3-flow theorem on 11-edge-connected signed graphs. [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]

In this paper we are interested in algorithms for finding 2-factors that cover certain prescribed edge-cuts in bridgeless cubic graphs. Since a Hamilton cycle is a 2-factor covering all edge-cuts, imposing the constraint of covering those edge-cuts makes the obtained 2-factor closer to a Hamilton cycle. We present an algorithm for finding a minimum-weight 2-factor covering all the 3-edge cuts in weighted bridgeless cubic graphs, together with a polyhedral description of such 2-factors and that of perfect matchings intersecting all the 3-edge cuts in exactly one edge. We further give an algorithm for finding a 2-factor covering all the 3- and 4-edge cuts in bridgeless cubic graphs. Both of these algorithms run in O(n³) time, where n is the number of vertices. As an application of the latter algorithm, we design a 6/5-approximation algorithm for finding a minimum 2-edge-connected spanning subgraph in 3-edge-connected cubic graphs, which improves upon the previous best ratio of 5/4. The algorithm begins with finding a 2-factor covering all 3- and 4-edge cuts, which is the bottleneck in terms of complexity, and thus it has running time O(n³). We then improve this time complexity to O(n²log4n) by relaxing the condition of the initial 2-factor and elaborating on the subsequent processes. [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]

A graph drawn in the plane is called k-quasi-planar if it does not contain k pair-wise crossing edges. It has been conjectured for a long time that for every fixed k, the maximum number of edges of a k-quasi-planar graph with n vertices is O(n). The best known upper bound is n(logn)O(logk). In the present paper, we improve this bound to (n log n)2α(n)ck in the special case where the graph is drawn in such a way that every pair of edges meet at most once. Here α(n) denotes the (extremely slowly growing) inverse of the Ackermann function. We also make further progress on the conjecture for k-quasi-planar graphs in which every edge is drawn as an x-monotone curve. Extending some ideas of Valtr, we prove that the maximum number of edges of such graphs is at most 2ck6 n log n. [ABSTRACT FROM AUTHOR]

Reed's w, Δ, χ conjecture proposes that every graph satisfies χ ≤ [1/2(Δ + 1 + w)] it is known to hold for all claw-free graphs. In this paper we consider a local strengthening of this conjecture. We prove the local strengthening for line graphs, then note that previous results immediately tell us that the local strengthening holds for all quasi-line graphs. Our proofs lead to polytime algorithms for constructing colorings that achieve our bounds: O(n²) for line graphs and O(n³m²) for quasi-line graphs. For line graphs, this is faster than the best known algorithm for constructing a coloring that achieves the bound of Reed's original conjecture. [ABSTRACT FROM AUTHOR]

The classical Feedback Vertex Set problem asks, for a given undirected graph G and an integer k, to find a set of at most k vertices that hits all the cycles in the graph G. Feedback Vertex SET has attracted a large amount of research in the parameterized setting, and subsequent fixed-parameter and kernelization algorithms have been a rich source of ideas in the field. In this paper we consider a more general and difficult version of the problem, named Subset Feedback Vertex SET (Subset-FVS), where an instance comes additionally with a set S ⊆ V of vertices, and we ask for a set of at most k vertices that hits all simple cycles passing through S. Because of its applications in circuit testing and genetic linkage analysis, Subset-FVS was studied from the approximation algorithm perspective by Even et al. [SIAM J. Discrete Math., 13 (2000), pp. 225-267; SIAM J. Comput., 30 (2000), pp. 1231-1252]. The question of whether the Subset-FVS problem is fixed-parameter tractable was posed independently by Kawarabayashi and Saurabh in 2009. We answer this question affirmatively. We begin by showing that this problem is fixed-parameter tractable when parameterized by |S|. Next we present an algorithm which reduces the given instance to 2knO(1) instances with the size of S bounded by O(k³), using kernelization techniques such as the 2-expansion lemma, Menger's theorem, and Gallai's theorem. These two facts allow us to give a 2O(k log k)nO(1) time algorithm solving the Subset-FVS problem, proving that it is indeed fixed-parameter tractable. [ABSTRACT FROM AUTHOR]

In 1972, Woodall raised the following Ore-type condition for directed Hamilton cycles in digraphs: Let D be a digraph. If for every vertex pair u and v, where there is no arc from u to v, we have d+(u) + d-(v) ≥ |D|, then D has a directed Hamilton cycle. By a correspondence between bipartite graphs and digraphs, the above result is equivalent to the following result of Las Vergnas: Let G = (B, W) be a balanced bipartite graph. If for any b ∈ B and w ∈ W, where b and w are nonadjacent, we have d(w) + d(b) ≥ |G|/2 + 1, then every perfect matching of G is contained in a Hamilton cycle. The lower bounds in both results are tight. In this paper, we reduce both bounds by 1 and prove that the conclusions still hold, with only a few exceptional cases that can be clearly characterized. [ABSTRACT FROM AUTHOR]

For a spanning tree T of a graph G, we define the total excess te(T, k) of T from k as te(T, k) := ∑v∈(T) max{dT(v) -- k, 0}, where dT(v) is the degree of a vertex v in T. In this paper, we show the following: if G is a 3-connected graph on a surface with Euler characteristic x < 0, then G has a spanning [8-2x/3]-tree T with te(T, 3) ≤ -2x -- 1. We also show an application of this theorem to finding "light" connected subgraphs in a 3-connected graph on a surface. [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]

Detecting and counting the number of copies of certain subgraphs (also known as network motifs or graphlets) is motivated by applications in a variety of areas ranging from biology to the study of the World Wide Web. Several polynomial-time algorithms have been suggested for counting or detecting the number of occurrences of certain network motifs. However, a need for more efficient algorithms arises when the input graph is very large, as is indeed the case in many applications of motif counting. In this paper we design sublinear-time algorithms for approximating the number of copies of certain constant-size subgraphs in a graph G. That is, our algorithms do not read the whole graph, but rather query parts of the graph. Specifically, we consider algorithms that may query the degree of any vertex of their choice and may ask for any neighbor of any vertex of their choice. The main focus of this work is on the basic problem of counting the number of length-2 paths and more generally on counting the number of stars of a certain size. Specifically, we design an algorithm that, given an approximation parameter 0 < ε < 1 and query access to a graph G, outputs an estimate … such that with high constant probability, Due to image rights restrictions, multiple line equation(s) cannot be graphically displayed., where v8(G) denotes the number of stars of size s + 1 in the graph. The expected query complexity and running time of the algorithm are Due to image rights restrictions, multiple line equation(s) cannot be graphically displayed.. We also prove lower bounds showing that this algorithm is tight up to polylogarithmic factors in n and the dependence on ε. Our work extends the work of Feige [SIAM J. Comput., 35 (2006), pp. 964-984] and Goldreich and Ron [Random Structures Algorithms, 32 (2008), pp. 473-493] on approximating the number of edges (or average degree) in a graph. Combined with these results, our result can be used to obtain an estimate on the variance of the degrees in the graph and corresponding higher moments. In addition, we give some (negative) results on approximating the number of tri- angles and on approximating the number of length-3 paths in sublinear-time. [ABSTRACT FROM AUTHOR]

A graph is polar if its vertex set can be partitioned into A and B in such a way that A induces a complete multipartite graph and B induces a disjoint union of cliques (i.e., the complement of a complete multipartite graph). Polar graphs naturally generalize several classes of graphs such as bipartite, cobipartite, and split graphs. The problem of recognizing polar graphs is NP-complete in general. However, it has been shown to be polynomial for several classes of graphs, including cographs and chordal graphs. In this paper, we study the problem of recognizing graphs whose line graphs are polar. It turns out that the core part of this problem lies in determining whether the edge set of a graph admits a partition (A, B) so that A induces a P3-free subgraph (i.e., a matching) and B induces a P4-free subgraph. We give a structural characterization of such graphs. The characterization enables us to devise an O(n) time algorithm to solve the stated recognition problem. [ABSTRACT FROM AUTHOR]

For a family S of graphs, let ω(S) be the supremum of t : 1 < t ⩽ 2 such that P(G, λ) ≠ 0 for all G ϵ S and all λ ϵ (1, t). In this paper we show that ω(S) = ω(S ∩κ) for any family S of graphs satisfying certain conditions, where κ` is a special family of graphs. This result makes it much easier to determine ω(S) for such families S. [ABSTRACT FROM AUTHOR]

In this paper, we provide a detailed comparison between a fully randomized protocol for rumor spreading on a complete graph and a quasirandom protocol introduced by Doerr, Friedrich, and Sauerwald [Quasirandom rumor spreading, in Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, SIAM, Philadelphia, 2008, pp. 773-781]. In the former, initially there is one vertex which holds a piece of information, and during each round every one of the informed vertices chooses uniformly at random and independently one of its neighbors and informs it. In the quasirandom version of this method (cf. Doerr, Friedrich, and Sauerwald) each vertex has a cyclic list of its neighbors. Once a vertex has been informed, it chooses uniformly at random only one neighbor. In the following round, it informs this neighbor, and at each subsequent round it picks the next neighbor from its list and informs it. We give a precise analysis of the evolution of the quasirandom protocol on the complete graph with n vertices and show that it evolves essentially in the same way as the randomized protocol. In particular, if S(n) denotes the number of rounds that are needed until all vertices are informed, we show that for any slowly growing function w(n), we have log2 n + ln n - 4 ln ln n ≤ S(n) = log2 n + ln n + w(n), with probability 1 - o(1). [ABSTRACT FROM AUTHOR]

A graph is an interval graph if it is the intersection graph of intervals on a line. Interval graphs are known to be the intersection of chordal graphs and asteroidal triple-free graphs, two families where the well-known lexicographic breadth first search (LBFS) plays an important algorithmic and structural role. In this paper we show that interval graphs have a very rich LBFS structure and that by exploiting this structure one can design a linear time, easily implementable, interval graph recognition algorithm. [ABSTRACT FROM AUTHOR]

A digraph is upward planar if it admits a planar drawing where all edges are monotone in the upward direction. It is known that the problem of testing a digraph for upward planarity is NP-complete in general. This paper describes an O(n4)-time upward planarity testing algorithm for all digraphs that have a series-parallel structure, where n is the number of vertices of the input. This significantly enlarges the family of digraphs for which a polynomial-time testing algorithm is known. Furthermore, the study is extended to general digraphs, and a fixed parameter tractable algorithm for upward planarity testing is described, whose time complexity is O(dt · t · n3 + d · t2 · n + d2 · n2) where t is the number of triconnected components of the digraph and d is an upper bound on the diameter of any split component of the digraph. Our results use the new notion of upward spirality that, informally speaking, is a measure of the "level of winding" that a triconnected component of a digraph G can have in an upward planar drawing of G. [ABSTRACT FROM AUTHOR]

We consider the following firefighter problem on a graph G = (V,E). Initially, a fire breaks out at a vertex υ of G. In each subsequent time unit, a firefighter protects one vertex, and then the fire spreads to all unprotected neighbors of the vertices on fire. The objective of the firefighter is to save as many vertices as possible. Let sn(υ) denote the maximum number of vertices the firefighter can save when a fire breaks out at vertex υ of G. We define the surviving rate ρ(G) of G to be the average percentage of vertices that can be saved when a fire randomly breaks out at a vertex of G, i.e., ρ(G) = Συ∈ν sn(υ)/n2. In this paper, we prove that for every tree T on n vertices, ρ(T) > 1 - √2/n. Furthermore, we show that ρ(G) > 1/6 for every outerplanar graph G, and ρ(H) > 3/10 for every Halin graph H with at least 5 vertices. [ABSTRACT FROM AUTHOR]

An r–labeling of the vertices of a graph G = (V (G), E(G)), f : V (G) –→ (1, 2, . . . , r), is said to be distinguishing provided that no nontrivial automorphism of G preserves all of the vertex labels. The distinguishing number of G, denoted by D(G), is the minimum r such that G has a distinguishing r–labeling. The distinguishing chromatic number ?D(G) of G is defined similarly, where, in addition, f is assumed to be a proper coloring. In this paper, we determine D(G) and ?D(G) of the book graph Bm,n, and ?D(G) of the generalized Petersen graph Pn,k. [ABSTRACT FROM AUTHOR]

The regularity lemma of Szemerédi gives a concise approximate description of a graph via a so-called regular partition of its vertex set. In this paper we address the following problem: Can a graph have two "distinct" regular partitions? It turns out that (as observed by several researchers) for the standard notion of a regular partition, one can construct a graph that has very distinct regular partitions. On the other hand, we show that for the stronger notion of a regular partition that has been recently studied, all such regular partitions of the same graph must be very "similar." En route, we also give a short argument for deriving a recent variant of the regularity lemma obtained independently by Rödl and Schacht and by Lovász and Szegedy from a previously known variant of the regularity lemma due to Alon et al. in 2000. The proof also provides a deterministic polynomial time algorithm for finding such partitions. [ABSTRACT FROM AUTHOR]

In this paper we study the integrity of certain graph families. These include planar graphs, graphs with a given genus, graphs on the d-dimensional integer lattice ℤd, and graphs that have no Kh-minor. We give upper bounds for the integrity in terms of the order n of the graph. We also give lower bounds for box-graphs in ℤd. As a consequence, the integrity of planar graphs is on the order of n2/3, where 2/3 is the best possible exponent. [ABSTRACT FROM AUTHOR]

Given positive integers k and d, a graph G is said to be (k, d)*-colorable if the vertices of G can be colored with k colors such that every vertex has at most d neighbors receiving the same color as itself. Let G be the family of plane graphs with neither adjacent triangles nor cycles of length 5. It is proved in this paper that every graph in G is (3, 1)*-colorable. This result is sharp in the sense that there exist non-(2, 1)*-colorable plane graphs with neither triangles nor cycles of length 5. As a corollary, after removing a matching, every graph in G is 3-colorable. This provides a partial solution to a conjecture of Borodin and Raspaud [J. Combin. Theory Ser. B, 93 (2003), pp. 17-27]. [ABSTRACT FROM AUTHOR]