Covering minimum spanning trees of random subgraphs

We consider the problem of finding a sparse set of edges containing the minimum spanning tree (MST) of a random subgraph of G with high probability. The two random models that we consider are subgraphs induced by a random subset of vertices, each vertex included independently with probability p, and subgraphs generated as a random subset of edges, each edge with probability p. Let n denote the number of vertices, choose p ∈ (0, 1) possibly depending on n, and let b = 1/(1 ? p). We show that in both random models, for any weighted graph G, there is a set of edges Q of cardinality O(n log_bn) that contains the minimum spanning tree of a random subgraph of G with high probability. This result is asymptotically optimal. As a consequence, we also give a bound of O(kn) on the size of the union of all minimum spanning trees of G with some k vertices (or edges) removed. More generally, we show a bound of O(n log_bn) on the size of a covering set in a matroid of rank n, which contains the minimum‐weight basis of a random subset with high probability. Also, we give a randomized algorithm that calls an MST subroutine only a polylogarithmic number of times and finds the covering set with high probability. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Complete subgraphs with large degree sums

Let t(n, k) denote the Turán number—the maximum number of edges in a graph on n vertices that does not contain a complete graph K_k+1. It is shown that if G is a graph on n vertices with n ≥ k²(k – 1)/4 and m < t(n, k) edges, then G contains a complete subgraph K_k such that the sum of the degrees of the vertices is at least 2km/n. This result is sharp in an asymptotic sense in that the sum of the degrees of the vertices of K_k is not in general larger, and if the number of edges in G is at most t(n, k) – ? (for an appropriate ?), then the conclusion is not in general true. © 1992 John Wiley & Sons, Inc.     

2-Colored triangles in edge-colored complete graphs, II

The largest number n = n(k) for which there exists a k-coloring of the edges of k_n with every triangle 2-colored is found to be n(k) = 2^r5^m, where k = 2m + r and r = 0 or 1, and all such colorings are given. We also prove the best possible result that a k-colored K_p satisfying 1 < k < 1 + √p contains at most k − 2 vertices not in a bichromatic triangle.     

Order and chaos in Hofstadter's Q(n) sequence

A number of observations are made on Hofstadter's integer sequence defined by Q(n) = Q(n − Q(n − 1)) + Q(n − Q(n − 2)), for n > 2, and Q(1) = Q(2) = 1. On short scales, the sequence looks chaotic. It turns out, however, that the Q(n) can be grouped into a sequence of generations. The k‐th generation has 2^k members that have “parents” mostly in generation k − 1 and a few from generation k − 2. In this sense, the sequence becomes Fibonacci type on a logarithmic scale. The variance of S(n) = Q(n) − n/2, averaged over generations, is ≅2^αk, with exponent α = 0.88(1). The probability distribution p*(x) of x = R(n) = S(n)/n^α, n ≫ 1, is well defined and strongly non‐Gaussian, with tails well described by the error function erfc. The probability distribution of x_m = R(n) − R(n − m) is given by p_m(x_m) = λ_m p*(x_m/λ_m), with λ_m → √2 for large m. © 1999 John Wiley & Sons, Inc.     

On the Number of Edges in Colour-Critical Graphs and Hypergraphs

A (hyper)graph G is called k-critical if it has chromatic number k, but every proper sub(hyper)graph of it is (k-1)-colourable. We prove that for sufficiently large k, every k-critical triangle-free graph on n vertices has at least (k-o(k))n edges. Furthermore, we show that every (k+1)-critical hypergraph on n vertices and without graph edges has at least (k-3/³?{k}) n(k-3/\sqrt[3]{k}) n edges. Both bounds differ from the best possible bounds by o(kn) even for graphs or hypergraphs of arbitrary girth.     

Rainbows in the Hypercube

Let Q_n be a hypercube of dimension n, that is, a graph whose vertices are binary n-tuples and two vertices are adjacent iff the corresponding n-tuples differ in exactly one position. An edge coloring of a graph H is called rainbow if no two edges of H have the same color. Let f(G,H) be the largest number of colors such that there exists an edge coloring of G with f(G,H) colors such that no subgraph isomorphic to H is rainbow. In this paper we start the investigation of this anti-Ramsey problem by providing bounds on f(Q_n,Q_k) which are asymptotically tight for k = 2 and by giving some exact results.     

Q5‐factorization of λKn

Q_k is the simple graph whose vertices are the k‐tuples with entries in {0, 1} and edges are the pairs of k‐tuples that differ in exactly one position. In this paper, we proved that there exists a Q₅‐factorization of λK_n if and only if (a) n ≡ 0(mod 32) if λ ≡ 0(mod 5) and (b) n ≡ 96(mod 160) if λ ? 0(mod 5).     

A note on a conjecture about cycles with many incident chords

Given positive integers n and k, let g_k(n) denote the maximum number of edges of a graph on n vertices that does not contain a cycle with k chords incident to a vertex on the cycle. Bollobás conjectured as an exercise in [2, p. 398, Problem 13] that there exists a function n(k) such that g_k(n) = (k + 1)n ? (k + 1)² for all n ≥ n(k). Using an old result of Bondy [ 3 ], we prove the conjecture, showing that n(k) ≤ 3 k + 3. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 180–182, 2004     

Approximation of monomials by lower degree polynomials

Our topic is the uniform approximation ofx ^k by polynomials of degreen (n on the interval [–1, 1]. Our major result indicates that good approximation is possible whenk is much smaller thann ² and not possible otherwise. Indeed, we show that the approximation error is of the exact order of magnitude of a quantity,p _k,n , which can be identified with a certain probability. The numberp _k,n is in fact the probability that when a (fair) coin is tossedk times the magnitude of the difference between the number of heads and the number of tails exceedsn.     

A spectral heuristic for bisecting random graphs

The minimum bisection problem is to partition the vertices of a graph into two classes of equal size so as to minimize the number of crossing edges. Computing a minimum bisection is NP‐hard in the worst case. In this paper we study a spectral heuristic for bisecting random graphs G_n(p,p′) with a planted bisection obtained as follows: partition n vertices into two classes of equal size randomly, and then insert edges inside the two classes with probability p′ and edges crossing the partition with probability p independently. If , where c₀ is a suitable constant, then with probability 1 ? o(1) the heuristic finds a minimum bisection of G_n(p,p′) along with a certificate of optimality. Furthermore, we show that the structure of the set of all minimum bisections of G_n(p,p′) undergoes a phase transition as . The spectral heuristic solves instances in the subcritical, the critical, and the supercritical phases of the phase transition optimally with probability 1 ? o(1). These results extend previous work of Boppana 5 . © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Subgraphs of colour-critical graphs

Some problems and results on the distribution of subgraphs in colour-critical graphs are discussed. In section 3 arbitrarily largek-critical graphs withn vertices are constructed such that, in order to reduce the chromatic number tok−2, at leastc _k n ² edges must be removed. In section 4 it is proved that a 4-critical graph withn vertices contains at mostn triangles. Further it is proved that ak-critical graph which is not a complete graph contains a (k−1)-critical graph which is not a complete graph.     

An application of the combinatorial Nullstellensatz to a graph labelling problem

An antimagic labelling of a graph G with m edges and n vertices is a bijection from the set of edges of G to the set of integers {1,…,m}, such that all n vertex sums are pairwise distinct, where a vertex sum is the sum of labels of all edges incident with that vertex. A graph is called antimagic if it admits an antimagic labelling. In N. Hartsfield and G. Ringle, Pearls in Graph Theory, Academic Press, Inc., Boston, 1990, Ringel has conjectured that every simple connected graph, other than K₂, is antimagic. In this article, we prove a special case of this conjecture. Namely, we prove that if G is a graph on n=p^k vertices, where p is an odd prime and k is a positive integer that admits a C_p‐factor, then it is antimagic. The case p=3 was proved in D. Hefetz, J Graph Theory 50 (2005), 263–272. Our main tool is the combinatorial Nullstellensatz [N. Alon, Combin Probab Comput 8(1–2) (1999), 7–29]. © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 70–82, 2010.     

On quadrilaterals in layers of the cube and extremal problems for directed and oriented graphs

Erdős has conjectured that every subgraph of the n‐cube Q_n having more than (1/2 + o(1))e(Q_n) edges will contain a 4‐cycle. In this note we consider ‘layer’ graphs, namely, subgraphs of the cube spanned by the subsets of sizes k − 1, k and k + 1, where we are thinking of the vertices of Q_n as being the power set of {1,…, n}. Observe that every 4‐cycle in Q_n lies in some layer graph. We investigate the maximum density of 4‐cycle free subgraphs of layer graphs, principally the case k = 2. The questions that arise in this case are equivalent to natural questions in the extremal theory of directed and undirected graphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 66–82, 2000     

含故障点的加强超立方体中路和圈的嵌入

本文研究了含故障点的n-维加强超立方体Q_n,k中的路和圈嵌入的问题.充分分析了加强超立方体网络的潜在特性,利用了构造的方法.得到了含2n-4个故障点的加强超立方体Q_n,k中含长为2ⁿ-2f的容错圈的结论,推广了折叠超立方体网络中1-点容错圈嵌入的结果.其中折叠超立方体网络为加强超立方体网络的一种特殊情况.     

PATHS AND CYCLES EMBEDDING ON FAULTY ENHANCED HYPERCUBE NETWORKS

Let Qn,k(n≥3,1≤k≤n-1) be an n-dimensional enhanced hypercube which is an attractive variant of the hypercube and can be obtained by adding some complementary edges,fv and fe be the numbers of faulty vertices and faulty edges,respectively.In this paper,we give three main results.First,a fault-free path P [u,v] of length at least 2n-2fv-1(respectively,2n-2fv-2) can be embedded on Qn,k with fv+fe≤n-1 when d Qn,k(u,v) is odd(respectively,d Qn,k(u,v) is even).Secondly,an Qn,k is(n-2) edgefault-free hyper Hamiltonian-laceable when n(≥3) and k have the same parity.Lastly,a fault-free cycle of length at least 2n-2fv can be embedded on Qn,k with fe≤n-1 and fv+fe≤2n-4.     

Phase transition of the minimum degree random multigraph process

We study the phase transition of the minimum degree multigraph process. We prove that for a constant h_g ≈︁ 0.8607, with probability tending to 1 as n → ∞, the graph consists of small components on O(log n) vertices when the number of edges of a graph generated so far is smaller than h_gn, the largest component has order roughly n^2/3 when the number of edges added is exactly h_gn, and the graph consists of one giant component on Θ(n) vertices and small components on O(log n) vertices when the number of edges added is larger than h_gn. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

Erratum to: On the Extremal Zagreb Indices of Graphs with Cut Edges

For a (molecular) graph, the first Zagreb index M ₁ is equal to the sum of squares of the vertex degrees, and the second Zagreb index M ₂ is equal to the sum of products of degrees of pairs of adjacent vertices. In this paper, we show that all connected graphs with n vertices and k cut edges, the maximum (resp. minimum) M ₁- and M ₂-value are obtained, respectively, and uniquely, at K _n ^k (resp. P _n ^k ), where K _n ^k is a graph obtained by joining k independent vertices to one vertex of K _n−k and P _n ^k is a graph obtained by connecting a pendent path P _k+1 to one vertex of C _n−k .     

Fault-tolerant panconnectivity of augmented cubes

The augmented cube AQ _n is a variation of the hypercube Q _n . This paper considers the panconnectivity of AQ _n (n ⩾ 3) with at most 2n−5 faulty vertices and/or edges and shows that, for any two fault-free vertices u and v with distance d in AQ _n , there exist fault-free uv-paths of every length from d + 2 to 2 ⁿ − f − 1, where f is the number of faulty vertices in AQ _n . The proof is based on an inductive construction.     

Matching extension in the powers of n-connected graphs

Let G be a graph on p vertices. Then for a positive integer n₁ G is said to be n-extendible if (i) n < p/2, (ii) G has a set of n independent edges, and (iii) every such set is contained in a perfect matching of G. In this paper we will show that if p is even and G is n-connected, then G^k is -extendible for every integer k ≥ 2 such that . © 1996 John Wiley & Sons, Inc.     

Some Algebraic Methods for Calculating the Number of Colorings of a Graph

With an arbitrary graph G having n vertices and m edges, and with an arbitrary natural number p, we associate in a natural way a polynomial R(x ₁,...,x _n) with integer coefficients such that the number of colorings of the vertices of the graph G in p colors is equal to p ^m-n R(0,...,0). Also with an arbitrary maximal planar graph G, we associate several polynomials with integer coefficients such that the number of colorings of the edges of the graph G in 3 colors can be calculated in several ways via the coefficients of each of these polynomials. Bibliography: 2 titles.