Search

Given an n vertex graph whose edges have colored from one of τ colors C = {ci, C2,..., cr}, we define the Hamilton cycle color profile hcp(G) to be the set of vectors (mi, m2,..., mr) ∈ [0, n}r such that there exists a Hamilton cycle that is the concatenation of τ paths Pi, P2, ∙.., Pr, where Pi contains rΠι edges of color cι. We study hcp(Gn p) when the edges are randomly colored. We discuss the profile close to the threshold for the existence of a Hamilton cycle and the threshold for when ∕icp(Gnjf>) = {(mι, m2,..., mr) ∈ [0,n]r: mi + m2 + ∙ ∙ ∙ + mr = n}. [ABSTRACT FROM AUTHOR]

For an undirected graph or multigraph G = (V, E) and a function f : V → ℤ+, an f-factor is a subgraph whose degree function is f. For integral edge weights of maximum magnitude W our algorithm finds a maximum weight f-factor in time Õ(Wf(V)ω), where f(V ) = ∑v∈V f(v) and ω is the exponent of matrix multiplication. The algorithm is randomized and has two versions. For worst-case time the algorithm is correct with high probability. For expected time the algorithm is Las Vegas. The algorithm is based on a detailed analysis of the structure of the optimum blossoms. A special case gives a representation for single-source shortest-paths in conservative undirected graphs, generalizing the standard shortest-path tree to a "tree of cycles". The representation can be constructed by a randomized algorithm with the same time bound as above, or deterministically by an algorithm for maximum weight matching, achieving time O(n(m+n log n)) or O(√n mlog (nW)). [ABSTRACT FROM AUTHOR]

An undirected graph G is d-degenerate if every subgraph of G has a vertex of degree at most d. By the classical theorem of Erdös and Gallai from 1959, every graph of degeneracy d > 1 contains a cycle of length at least d + 1. The proof of Erdös and Gallai is constructive and can be turned into a polynomial time algorithm constructing a cycle of length at least d + 1. But can we decide in polynomial time whether a graph contains a cycle of length at least d + 2? An easy reduction from Hamiltonian Cycle provides a negative answer to this question: Deciding whether a graph has a cycle of length at least d+2 is NP-complete. Surprisingly, the complexity of the problem changes drastically when the input graph is 2-connected. In this case we prove that deciding whether G contains a cycle of length at least d + k can be done in time 2O(k) .| V (G)| O(1). In other words, deciding whether a 2-connected n-vertex G contains a cycle of length at least d+log n can be done in polynomial time. Similar algorithmic results hold for long paths in graphs. We observe that deciding whether a graph has a path of length at least d+1 is NP-complete. However, we prove that if graph G is connected, then deciding whether G contains a path of length at least d+k can be done in time 2O(k) .nO(1). We complement these results by showing that the choice of degeneracy as the ``above guarantee parameterization"" is optimal in the following sense: For any ε > 0 it is NP-complete to decide whether a connected (2-connected) graph of degeneracy d has a path (cycle) of length at least (1 + ε )d. [ABSTRACT FROM AUTHOR]

Given an undirected graph and two pairs of vertices (si, ti) for i ∈{ 1, 2\} we show that there is a polynomial time Monte Carlo algorithm that finds disjoint paths of smallest total length joining si and ti for i ∈{ 1, 2\}, respectively, or concludes that there most likely are no such paths at all. Our algorithm applies to both the vertex- and edge-disjoint versions of the problem. Our algorithm is algebraic and uses permanents over the polynomial ring Z4[X] in combination with the isolation lemma of Mulmuley, Vazirani, and Vazirani to detect a solution. To this end, we develop a fast algorithm for permanents over the ring Zt[X], where t is a power of 2, by modifying Valiant's 1979 algorithm for the permanent over Zt. [ABSTRACT FROM AUTHOR]

We consider the existence of patterned Hamilton cycles in randomly colored random graphs. Given a string π over a set of colors { 1, 2, . . . , r}, we say that a Hamilton cycle is π -colored if the pattern repeats at intervals of length |π| as we go around the cycle. We prove a hitting time result for the existence of such a cycle. We also prove a hitting time result for the related notion of π -connected. [ABSTRACT FROM AUTHOR]

For any r ≥ 2 and k ≥ 3, the r-color size-Ramsey number R(G,r) of a k-uniform hypergraph G is the smallest integer m such that there exists a k-uniform hypergraph H on m edges such that any coloring of the edges of H with r colors yields a monochromatic copy of G. Let Pn,k-1 (k) denote the k-uniform tight path on n vertices. Dudek et al. [J. Graph Theory, 86 (2017), pp. 104-121] showed that the size-Ramsey number of tight paths R(Pn,k-1 (k), 2) = O(nk-1-α(logn)1+α) where α = (k-2)/2k-1 +1. In this paper, we improve their bound by showing that R(Pn,k-1(k), r) = O(rk(nlogn)k/2) for all k ≥ 3 and r ≥ 2. [ABSTRACT FROM AUTHOR]

The Chordal Vertex Deletion (CHVD) problem asks to delete a minimum number of vertices from an input graph to obtain a chordal graph. In this paper we develop a polynomial kernel for CHVD under the parameterization by the solution size. Using a new Erdõs-Pósa-type packing/covering duality for holes in nearly chordal graphs, we present a polynomial-time algorithm that reduces any instance (G, k) of CHVD to an equivalent instance with poly(k) vertices. The existence of a polynomial kernel answers an open problem posed by Marx in 2006 [D. Marx, "Chordal Deletion Is Fixed-Parameter Tractable," in Graph-Theoretic Concepts in Computer Science, Lecture Notes in Comput. Sci. 4271, Springer, 2006, pp. 37-48]. To obtain the kernelization, we develop the first poly(opt)-approximation algorithm for CHVD, which is of independent interest. In polynomial time, it either decides that G has no chordal deletion set of size k, or outputs a solution of size O(k4log² k). [ABSTRACT FROM AUTHOR]

Inside a two-dimensional region ("cake"), there are m nonoverlapping tiles of a certain kind ("toppings"). We want to expand the toppings while keeping them nonoverlapping, and possibly add some blank pieces of the same "certain kind," such that the entire cake is covered. How many blanks must we add? We study this question in several cases: (1) The cake and toppings are general polygons. (2) The cake and toppings are convex figures. (3) The cake and toppings are axis-parallel rectangles. (4) The cake is an axis-parallel rectilinear polygon and the toppings are axis-parallel rectangles. In all four cases, we provide tight bounds on the number of blanks. [ABSTRACT FROM AUTHOR]

We prove an upper bound on the Shannon capacity of a graph via a linear programming variation. We show that our bound can outperform both the Lov\'asz theta number and the Haemers minimum rank bound. As a by-product, we also obtain a new upper bound on the broadcast rate of index coding. [ABSTRACT FROM AUTHOR]

For given simple graphs G1 and G2, the size Ramsey number Ȓ(G1,G2) is the smallest positive integer m, where there exists a graph G with m edges such that in any edge coloring of G with two colors red and blue, there is either a red copy of G1 or a blue copy of G2. In 1981, Erdös and Faudree investigated the size Ramsey number Ȓ(Kn, tK2), where Kn is a complete graph on n vertices and tK2 is a matching of size t. They obtained the value of Ȓ(Kn, tK2) when n ≥ 4t-1 as well as for t = 2 and asked for the behavior of these numbers when t is much larger than n. In this regard, they posed the following interesting question: For every positive integer n, is it true that ... In this paper, we obtain the exact value of Ȓ(Kn, tK2) for every pair of positive integers n, t, and as a byproduct, we give an affirmative answer to the question of Erdös and Faudree. [ABSTRACT FROM AUTHOR]

In this paper, we study the connectivity properties of the random subgraph of the n-cube generated by the k-out model and denoted by Qn(k). Let k be an integer, 1 ≤ k ≤ n-1. We let Qn(k) be the graph that is generated by independently including for every ν ∊ V(Qn) a set of k distinct edges chosen uniformly from all the (k n) sets of distinct edges that are incident to ν. We study the connectivity properties of Qn(k) as k varies. We show that without high probability (w.h.p.), Qn(1) does not contain a giant component i.e., a component that spans Ω(2n) vertices. Thereafter, we show that such a component emerges when k=2. In addition, the giant component spans all but o(2n) vertices, and hence it is unique. We then establish the connectivity threshold found at k0=log2 n-2log2log2 n. The threshold is sharp in the sense that Qn([k0]) is disconnected but Qn([k0]+1) is connected w.h.p. Furthermore, we show that w.h.p., Qn(k) is k-connected for every k≥ [k0]+1. [ABSTRACT FROM AUTHOR]

The rotor-router model is a deterministic process analogous to a simple random walk on a graph, and the discrepancy of token configurations between the rotor-router model and its corresponding random walk has been investigated in some contexts. Motivated by general Markov chains beyond simple random walks, this paper investigates a generalized model which imitates a Markov chain (of multiple tokens) possibly containing irrational transition probabilities. We are concerned with the vertexwise discrepancy of the numbers of tokens between the generalized model and its corresponding Markov chain, and present an upper bound of the discrepancy in terms of the mixing time of the Markov chain. [ABSTRACT FROM AUTHOR]

We first consider the following problem. We are given a fixed perfect matching M of [n] and we add random edges one at a time until there is a Hamilton cycle containing M. We show that with high probability (w.h.p.) the hitting time for this event is the same as that for the first time there are no isolated vertices in the graph induced by the random edges. We then use this result for the following problem. We generate random edges and randomly color them black or white. A path/cycle is said to be zebraic if the colors alternate along the path. We show that w.h.p. the hitting time for a zebraic Hamilton cycle coincides with every vertex meeting at least one edge of each color. We then consider some related problems and (partially) extend our results to multiple colors. We also briefly consider directed versions. [ABSTRACT FROM AUTHOR]

A key result in the field of kernelization, a subfield of parameterized complexity, states that the classic Disjoint Cycle Packing problem, i.e., finding k vertex disjoint cycles in a given graph G, admits no polynomial kernel unless NP ⊆ coNP/poly. However, very little is known about this problem beyond the aforementioned kernelization lower bound (within the parameterized complexity framework). In the hope of clarifying the picture and better understanding the types of constraints that separate kernelizable from nonkernelizable variants of Disjoint Cycle Packing, we investigate two relaxations of the problem. The first variant, which we call Almost Disjoint Cycle Packing, introduces a global relaxation parameter t. That is, given a graph G and integers k and t, the goal is to find at least k distinct cycles such that every vertex of G appears in at most t of the cycles. The second variant, Pairwise Disjoint Cycle Packing, introduces a local relaxation parameter, and we seek at least k distinct cycles such that every two cycles intersect in at most t vertices. While the Pairwise Disjoint Cycle Packing problem admits a polynomial kernel for all t ≥ 1, the kernelization complexity of Almost Disjoint Cycle Packing reveals an interesting spectrum of upper and lower bounds. In particular, for t = k/c, where c could be a function of k, we obtain a kernel of size O(2c² k7+c log³ k) whenever c ∈ o(√k). Thus the kernel size varies from being subexponential when c ∈ o(√k), to quasi-polynomial when c ∈ o(logℓ k), ℓ ∈ R+, and polynomial when c ∈ O(1). We complement these results for Almost Disjoint Cycle Packing by showing that the problem does not admit a polynomial kernel whenever t ∈ O(k∈) for any 0≤∈< 1, unless NP 埦 coNP/poly. [ABSTRACT FROM AUTHOR]

For a simple (unbiased) random walk on a connected graph with n vertices, the cover time (the expected number of steps it takes to visit all vertices) is at most O(n³). We consider locally biased random walks, in which the probability of traversing an edge depends on the degrees of its endpoints. We confirm a conjecture of Abdullah, Cooper, and Draief [2015] that the min-degree local bias rule ensures a cover time of O(n²). For this we formulate and prove the following lemma about spanning trees. Let R(e) denote for edge e the minimum degree among its two endpoints. We say that a weight function W for the edges is feasible if it is nonnegative, dominated by R (for every edge W(e) ≤ R(e)), and the sum over all edges of the ratios W(e)/R(e) equals n - 1. For example, in trees W(e) = R(e), and in regular graphs the sum of edge weights is d(n - 1). We will show in a lemma that for every feasible W, the minimum weight spanning tree has total weight O(n). For regular graphs, a similar lemma was proved by Kahn et al. (1989). [ABSTRACT FROM AUTHOR]

We present an algorithm for maintaining a maximal matching in a graph under addition and deletion of edges. Our algorithm is randomized and it takes expected amortized O(log n) time for each edge update, where n is the number of vertices in the graph. Moreover, for any sequence of t edge updates, the total time taken by the algorithm is O(t log n+n log² n) with high probability. [ABSTRACT FROM AUTHOR]

Gyárfás, Győri, and Simonovits [J. Comb., 7 (2016), pp. 205{216] proved that if a 3-uniform hypergraph with n vertices has no linear cycles, then its independence number α ≥ 2n/5. The hypergraph consisting of vertex disjoint copies of a complete hypergraph K3/5 on five vertices shows that equality can hold. They asked whether this bound can be improved if we exclude K3/5 as a subhypergraph and whether such a hypergraph is 2-colorable. In this paper, we answer these questions affirmatively. Namely, we prove that if a 3-uniform linear-cycle-free hypergraph doesn't contain K3 5 as a subhypergraph, then it is 2-colorable. This result clearly implies that its independence number α ≥ [n/2]. We show that this bound is sharp. Gyárfás, Gy}ori, and Simonovits also proved that a linear-cycle-free 3-uniform hypergraph contains a vertex of strong degree at most 2. In this context, we show that a linear-cycle-free 3-uniform hypergraph has a vertex of degree at most n - 2 when n ≥ 10. [ABSTRACT FROM AUTHOR]

Consider a directed analogue of the random graph process on n vertices, where the n(n - 1) edges are ordered uniformly at random and revealed one at a time. It is known that with high probability (w.h.p.) the first digraph in this process with both in-degree and out-degree ≥ q has a q-edge-coloring with a Hamilton cycle in each color. We show that this coloring can be constructed online, where each edge must be irrevocably colored as soon as it appears. In a similar fashion, for the undirected random graph process, we present an online n-edge-coloring algorithm which yields w.h.p. q disjoint rainbow Hamilton cycles in the first graph containing q disjoint Hamilton cycles. [ABSTRACT FROM AUTHOR]

A key feature of Simonovits' proof of the classic Erdőos--Pósa theorem is a simple subgraph of the host graph, a frame, that determines the outcome of the theorem. We transfer this frame technique to A-paths. With it we deduce a simple proof of Gallai's theorem, although with a worse bound, and we verify the Erdős--Pósa property for long and for even A-paths. We also show that even A-paths do not have the edge-Erdős--Pósa property. [ABSTRACT FROM AUTHOR]

The complexity of testing whether a graph contains an induced odd cycle of length at least five is currently unknown. In this paper we show that this test can be done in polynomial time if the input graph has no induced subgraph isomorphic to the bull (a triangle with two disjoint pendant edges). [ABSTRACT FROM AUTHOR]

In this paper, we give the following result: If D is a digraph of order n, and if d+ D(u)+d D(v) n for every two distinct vertices u and v with (u; v) =2 A(D), then D has a directed 2-factor with exactly k directed cycles of length at least 3, where n 12k+3. This result is equivalent to the following result: If G is a balanced bipartite graph of order 2n with partite sets X and Y , and if dG(x) + dG(y) n + 2 for every two vertices x 2 X and y 2 Y with xy =2 E(G), then for every perfect matching M, G has a 2-factor with exactly k cycles of length at least 6 containing every edge of M, where n 12k + 3. These results are generalizations of theorems concerning Hamilton cycles due to Woodall [Proc. Lond. Math. Soc., 24 (1972), pp. 739{755] and Las Vergnas [Problemes de couplages et problemes hamiltoniens en theorie des graphes, Ph.D. thesis, University of Paris, 1972], respectively. [ABSTRACT FROM AUTHOR]

We prove an ear-decomposition theorem for 4-edge-connected graphs and use it to prove that for every 4-edge-connected graph G and every r \in V (G), there is a set of four spanning trees of G with the following property. For every vertex in G, the unique paths back to r in each tree are edge-disjoint. Our proof implies a polynomial-time algorithm for constructing the trees. [ABSTRACT FROM AUTHOR]

Let L be a set of positive integers. We call a (directed) graph G an L-cycle graph if all cycle lengths in G belong to L. Let c(L; n) be the maximum number of cycles possible in an n-vertex L-cycle graph (we use ~c(L; n) for the number of cycles in directed graphs). In the undirected case we show that for any fixed set L, we have c(L; n) = (nbk=`c), where k is the largest element of L and 2` is the smallest even element of L (if L contains only odd elements, then c(L; n) = (n) holds). We also give a characterization of L-cycle graphs when L is a single element. In the directed case we prove that for any fixed set L, we have ~c(L; n) = (1 + o(1))( n 1 k 1 ) k 1, where k is the largest element of L. We determine the exact value of ~c(fkg; n) for every k and characterize all graphs attaining this maximum. [ABSTRACT FROM AUTHOR]

In this paper we determine the chromatic number of graphs with two odd cycle lengths. Let G be a graph and L(G) be the set of all odd cycle lengths of G. We prove that (1) if L(G) = f3; 3 + 2lg, where l ≥ 2, then x(G) = maxf3; !(G)g, and (2) if L(G) = fk; k + 2lg, where k ≥ 5 and l ≥ 1, then x(G) = 3. These, together with the case L(G) = f3; 5g solved in [S.-S. Wang, SIAM J. Discrete Math., 22 (2008), pp. 1040{1072] give a complete solution to the general problem addressed in [S.-S. Wang, SIAM J. Discrete Math., 22 (2008), pp. 1040{1072; S.-M. Camacho and I. Schiermeyer, Discrete Math., 309 (2009), pp. 4916{4919; and T. Kaiser, O. Rucký, and R. Škrekovski, SIAM J. Discrete Math., 25 (2011), pp. 1069{1088]. Our results also improve a classical theorem of Gyárfás which asserts that x (G) ≤ 2jL(G)j + 2 for any graph G. [ABSTRACT FROM AUTHOR]

The cyclability of a graph is the maximum integer k for which every k vertices lie on a cycle. The algorithmic version of the problem, given a graph G and a nonnegative integer k, decide whether the cyclability of G is at least k, is NP-hard. We study the parametrized complexity of this problem. We prove that this problem, parameterized by k, is co-W[1]-hard and that it does not admit a polynomial kernel on planar graphs, unless NP ⊆ co-NP=poly. On the positive side, we give an FPT algorithm for planar graphs that runs in time 22O(k2 log k). n2. Our algorithm is based on a series of graph-theoretical results on cyclic linkages in planar graphs. [ABSTRACT FROM AUTHOR]

Let G be an n-node simple directed planar graph with nonnegative edge weights. We study the fundamental problems of computing (1) a global cut of G with minimum weight and (2) a cycle of G with minimum weight. The best previously known algorithm for the former problem, running in O(n log³ n) time, can be obtained from the algorithm of Łącki, Nussbaum, Sankowski, and Wulff-Nilsen for single-source all-sinks maximum flows. The best previously known result for the latter problem is the O(n log³ n)-time algorithm of Wulff-Nilsen. By exploiting duality between the two problems in planar graphs, we solve both problems in O(n log n log log n) time via a divideand-conquer algorithm that finds a shortest nondegenerate cycle. The kernel of our result is an O(n log log n)-time algorithm for computing noncrossing shortest paths among nodes well ordered on a common face of a directed plane graph, which is extended from the algorithm of Italiano, Nussbaum, Sankowski, and Wulff-Nilsen for an undirected plane graph. [ABSTRACT FROM AUTHOR]

Let G be an interval graph and take one of its vertices x. Can we find in linear time a minimum number of vertex disjoint paths of G which cover the vertex set of G and have x as one of their endpoints? This paper provides a positive answer to this problem. In the course of developing such an algorithm, we explore the possibility of getting insight on the path structure of interval graphs via greedy graph searches. [ABSTRACT FROM AUTHOR]

We show that every bridgeless cubic graph G with m edges has a cycle cover of length at most 1.6m. Moreover, if G does not contain any intersecting circuits of length 5, then G has a cycle cover of length 212/135 ·m ≈ 1.570m, and if G contains no 5-circuits, then it has a cycle cover of length at most 14/9·m ≈ 1.556m. To prove our results, we show that each 2-edge-connected cubic graph G on n vertices has a 2-factor containing at most n/10+f(G) circuits of length 5, where the value of f(G) depends only on the presence of several subgraphs arising from the Petersen graph. As a corollary we get that each 3-edge-connected cubic graph on n vertices has a 2-factor containing at most n/9 circuits of length 5, and each 4-edge-connected cubic graph on n vertices has a 2-factor containing at most n/10 circuits of length 5. [ABSTRACT FROM AUTHOR]

Given a finite graph (network), let every node (cell) represent an individual dynamics given by a system of ordinary differential equations, and every arrow (edge) encode the dynamical influence of the tail node on the head node. We have then defined a coupled cell system that is associated with the given network structure. Subspaces that are defined by equalities of cell coordinates and left invariant under every coupled cell system respecting the network structure are called synchrony subspaces. They are completely determined by the network structure and form a complete lattice under set inclusions. We analyze the transition of the lattice of synchrony subspaces of a network that is caused by structural changes in the network topology, such as deletion and addition of cells or edges, and rewirings of edges. We give sufficient, and in some cases both sufficient and necessary, conditions under which lattice elements persist or disappear. [ABSTRACT FROM AUTHOR]

One of the most relevant tasks in network analysis is the detection of community structures, or clustering. Most popular techniques for community detection are based on the maximization of a quality function called modularity, which in turn is based upon particular quadratic forms associated to a real symmetric modularity matrix M, defined in terms of the adjacency matrix and a rank-one null model matrix. That matrix could be posed inside the set of relevant matrices involved in graph theory, alongside adjacency and Laplacian matrices. In this paper we analyze certain spectral properties of modularity matrices, which are related to the community detection problem. In particular, we propose a nodal domain theorem for the eigenvectors of M; we point out several relations occurring between the graph's communities and nonnegative eigenvalues of M; and we derive a Cheeger-type inequality for the graph modularity. [ABSTRACT FROM AUTHOR]