On the uniqueness of the graphs G(n, k) of the Johnson schemes

T. A. Dowling (J. Combin. Theory6 (1969), 251–263) proved the uniqueness of the graphs G(n, k) of the Johnson schemes for n > 2k(k ? 1) + 4. We improve this result by showing the uniqueness of G(n, k) for n > 4k.     

Hamiltonicity, independence number, and pancyclicity

A graph on n vertices is called pancyclic if it contains a cycle of length ? for all 3≤?≤n. In 1972, Erd?s proved that if G is a Hamiltonian graph on n>4k⁴ vertices with independence number k, then G is pancyclic. He then suggested that n=Ω(k²) should already be enough to guarantee pancyclicity. Improving on his and some other later results, we prove that there exists a constant c such that n>ck^7/3 suffices.     

On approximation of max-vertex-cover

We consider the max-vertex-cover (MVC) problem, i.e., find k vertices from an undirected and edge-weighted graph G=(V,E), where |V|=n⩾k, such that the total edge weight covered by the k vertices is maximized. There is a 3/4-approximation algorithm for MVC, based on a linear programming relaxation. We show that the guaranteed ratio can be improved by a simple greedy algorithm for k>(3/4)n, and a simple randomized algorithm for k>(1/2)n. Furthermore, we study a semidefinite programming (SDP) relaxation based approximation algorithms for MVC. We show that, for a range of k, our SDP-based algorithm achieves the best performance guarantee among the four types of algorithms mentioned in this paper.     

Topology of random clique complexes

In a seminal paper, Erd?s and Rényi identified a sharp threshold for connectivity of the random graph G(n,p). In particular, they showed that if p?logn/n then G(n,p) is almost always connected, and if p?logn/n then G(n,p) is almost always disconnected, as n→∞.The clique complexX(H) of a graph H is the simplicial complex with all complete subgraphs of H as its faces. In contrast to the zeroth homology group of X(H), which measures the number of connected components of H, the higher dimensional homology groups of X(H) do not correspond to monotone graph properties. There are nevertheless higher dimensional analogues of the Erd?s-Rényi Theorem.We study here the higher homology groups of X(G(n,p)). For k>0 we show the following. If p=n^α, with α<−1/k or α>−1/(2k+1), then the kth homology group of X(G(n,p)) is almost always vanishing, and if −1/k<α<−1/(k+1), then it is almost always nonvanishing.We also give estimates for the expected rank of homology, and exhibit explicit nontrivial classes in the nonvanishing regime. These estimates suggest that almost all d-dimensional clique complexes have only one nonvanishing dimension of homology, and we cannot rule out the possibility that they are homotopy equivalent to wedges of a spheres.     

Unavoidable subgraphs of colored graphs

A natural generalization of graph Ramsey theory is the study of unavoidable sub-graphs in large colored graphs. In this paper, we find a minimal family of unavoidable graphs in two-edge-colored graphs. Namely, for a positive even integer k, let S_k be the family of two-edge-colored graphs on k vertices such that one of the colors forms either two disjoint K_k/2's or simply one K_k/2. Bollobás conjectured that for all k and ε>0, there exists an n(k,ε) such that if n?n(k,ε) then every two-edge-coloring of K_n, in which the density of each color is at least ε, contains a member of this family. We solve this conjecture and present a series of results bounding n(k,ε) for different ranges of ε. In particular, if ε is sufficiently close to , the gap between our upper and lower bounds for n(k,ε) is smaller than those for the classical Ramsey number R(k,k).     

On 2-factors with k components

In this paper we study the minimum degree condition for a Hamiltonian graph to have a 2-factor with k components. By proving a conjecture of Faudree et al. [A note on 2-factors with two components, Discrete Math. 300 (2005) 218-224] we show the following. There exists a real number ε>0 such that for every integer k?2 there exists an integer n₀=n₀(k) such that every Hamiltonian graph G of order n?n₀ with has a 2-factor with k components.     

Non-Hamiltonian simple 3-polytopes having just two types of faces

It is shown that for every value of an integer k, k?11, there exist 3-valent 3-connected planar graphs having just two types of faces, pentagons and k-gons, and which are non- Hamiltonian. Moreover, there exist ?=?(k) > 0, for these values of k, and sequences (G_n)^∞_n=1 of the said graphs for which V(G_n)→∞ and the size of a largest circuit of G_n is at most (1??)V(G_n); similar result for the size of a largest path in such graphs is established for all k, k?11, except possibly for k = 14, 17, 22 and k = 5m+ 5 for all m?2.     

Connectivity of the uniform random intersection graph

A uniform random intersection graphG(n,m,k) is a random graph constructed as follows. Label each of n nodes by a randomly chosen set of k distinct colours taken from some finite set of possible colours of size m. Nodes are joined by an edge if and only if some colour appears in both their labels. These graphs arise in the study of the security of wireless sensor networks, in particular when modelling the network graph of the well-known key predistribution technique due to Eschenauer and Gligor.The paper determines the threshold for connectivity of the graph G(n,m,k) when n→∞ in many situations. For example, when k is a function of n such that k≥2 and m=⌊n^α⌋ for some fixed positive real number α then G(n,m,k) is almost surely connected when

lim infk²n/mlogn>1,     

The complexity of detecting fixed-density clusters

We study the complexity of finding a subgraph of a certain size and a certain density, where density is measured by the average degree. Let γ:N→Q₊ be any density function, i.e., γ is computable in polynomial time and satisfies γ(k)?k-1 for all k∈N. Then γ-CLUSTER is the problem of deciding, given an undirected graph G and a natural number k, whether there is a subgraph of G on k vertices that has average degree at least γ(k). For γ(k)=k-1, this problem is the same as the well-known CLIQUE problem, and thus NP-complete. In contrast to this, the problem is known to be solvable in polynomial time for γ(k)=2. We ask for the possible functions γ such that γ-CLUSTER remains NP-complete or becomes solvable in polynomial time. We show a rather sharp boundary: γ CLUSTER is NP-complete if γ=2+Ω(1/k^1-ε) for some ε>0 and has a polynomial-time algorithm for γ=2+O(1/k). The algorithm also shows that for γ=2+O(1/k^1-o(1)), γ-CLUSTER is solvable in subexponential time 2^no(1).     

On Samelson products in p-localized unitary groups

The unitary group U(n) has elements εi∈π2i+1(U(n)) (0?i?n−1) of its homotopy groups in the stable range. In this paper we show that certain multi Samelson products of type 〈εi,〈εj,εk〉〉 are non-trivial. This leads us to the result that the nilpotency class of the group of the self homotopy set [SU(n),SU(n)] is no less than 3, if 4?n. Also by the power of generalized Samelson products, we can see the further result that, for a prime p and an integer n=pk, nil[SU(n),SU(n)]_(p)?3, if (1) p?7 or (2) p=5 and n≡0 or 1mod4.     

Strong edge colorings of uniform graphs

For a graph G=(V(G),E(G)), a strong edge coloring of G is an edge coloring in which every color class is an induced matching. The strong chromatic index of G, χ_s(G), is the smallest number of colors in a strong edge coloring of G. The strong chromatic index of the random graph G(n,p) was considered in Discrete Math. 281 (2004) 129, Austral. J. Combin. 10 (1994) 97, Austral. J. Combin. 18 (1998) 219 and Combin. Probab. Comput. 11 (1) (2002) 103. In this paper, we consider χ_s(G) for a related class of graphs G known as uniform or ε-regular graphs. In particular, we prove that for 0<ε?d<1, all (d,ε)-regular bipartite graphs G=(U∪V,E) with |U|=|V|?n₀(d,ε) satisfy χ_s(G)?ζ(ε)Δ(G)², where ζ(ε)→0 as ε→0 (this order of magnitude is easily seen to be best possible). Our main tool in proving this statement is a powerful packing result of Pippenger and Spencer (Combin. Theory Ser. A 51(1) (1989) 24).     

On the value of a random minimum spanning tree problem

Suppose we are given a complete graph on n vertices in which the lenghts of the edges are independent identically distributed non-negative random variables. Suppose that their common distribution function F is differentiable at zero and D = F′ (0) > 0 and each edge length has a finite mean and variance. Let L_n be the random variable whose value is the length of the minimum spanning tree in such a graph. Then we will prove the following: lim_{n → ∞}E(L_n) = ζ(3)/D where ζ(3) = Σ_{k = 1}^∞ 1/k³ = 1.202… and for any ε > 0 lim_{n → ∞} Pr(|L_n^?ζ(3)/D|) > ε) = 0.     

Dense edge-magic graphs and thin additive bases

A graph G of order n and size m is edge-magic if there is a bijection l:V(G)∪E(G)→[n+m] such that all sums l(a)+l(b)+l(ab), ab∈E(G), are the same. We present new lower and upper bounds on M(n), the maximum size of an edge-magic graph of order n, being the first to show an upper bound of the form . Concrete estimates for ε can be obtained by knowing s(k,n), the maximum number of distinct pairwise sums that a k-subset of [n] can have.So, we also study s(k,n), motivated by the above connections to edge-magic graphs and by the fact that a few known functions from additive number theory can be expressed via s(k,n). For example, our estimate

     

Improvement on the Decay of Crossing Numbers

We prove that the crossing number of a graph decays in a “continuous fashion” in the following sense. For any ε > 0 there is a δ > 0 such that for a sufficiently large n, every graph G with n vertices and m ≥ n ^1+ε edges, has a subgraph G′ of at most (1 ? δ)m edges and crossing number at least (1 ? ε)CR(G). This generalizes the result of J. Fox and Cs. Tóth.     

Degree conditions for the partition of a graph into cycles, edges and isolated vertices

Let k,n be integers with 2≤k≤n, and let G be a graph of order n. We prove that if max{d_G(x),d_G(y)}≥(n−k+1)/2 for any x,y∈V(G) with x≠y and xy∉E(G), then G has k vertex-disjoint subgraphs H₁,…,H_k such that V(H₁)∪?∪V(H_k)=V(G) and H_i is a cycle or K₁ or K₂ for each 1≤i≤k, unless k=2 and G=C₅, or k=3 and G=K₁∪C₅.     

On a ramsey-type problem of J. A. Bondy and P. Erdös. I

Let m → (C_k, C_n) signify the truth of the following statement: Let {V(G); ≥ m; if G contains no C_k, then $\text{G}$ contains a C_n. Bondy and Erdös [1] proved that for n > 3 2n ? 1 → (C_n, C_n). They conjectured that 2n ? 1 → (C_n, C_k) for all n > 3 and all k < n and could prove it only for $\text{k < (2n)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$. In this paper we prove this for all n > 4 and for all k < n.     

On graphs critical with respect to vertex partition numbers

For k?0, ?_k(G) denotes the Lick-White vertex partition number of G. A graph G is called (n, k)-critical if it is connected and for each edge e of G?_k(G–e)<?_k(G)=n. We describe all (2, k)-critical graphs and for n?3,k?1 we extend and simplify a result of Bollobás and Harary giving one construction of a family of (n, k)-critical graphs of every possible order.     

Removable matchings and hamiltonian cycles

For a graph G, let σ₂(G) denote the minimum degree sum of two nonadjacent vertices (when G is complete, we let σ₂(G)=∞). In this paper, we show the following two results: (i) Let G be a graph of order n≥4k+3 with σ₂(G)≥n and let F be a matching of size k in G such that G−F is 2-connected. Then G−F is hamiltonian or G≅K₂+(K₂∪K_n−4) or ; (ii) Let G be a graph of order n≥16k+1 with σ₂(G)≥n and let F be a set of k edges of G such that G−F is hamiltonian. Then G−F is either pancyclic or bipartite. Examples show that first result is the best possible.     

Omega theorems for the iterated additive convolution of a nonnegative arithmetic function

Let R_k(n) denote the number of ways of representing the integers not exceeding n as the sum of k members of a given sequence of nonnegative integers. Suppose that $\text{1}\text{2}\text{< β < k}$, $\text{δ =}\text{β}\text{2}\text{?}\text{β}\text{(4}\text{min}\text{(β,}\text{k}\text{2}\text{))}$ and

$\text{ξ=}\text{1/2β if β<k/2,}\text{β?1/2 if β=1/2,}\text{(k ? 2)(k + 1)/2k if k/2<β<k.}$

R. C. Vaughan has shown that the relation R_k(n) = G(n) + o(n^δ log^?ξn) as n → +∞ is impossible when G(n) is a linear combination of powers of n and the dominant term of G(n) is cn^β, c > 0. P. T. Bateman, for the case k = 2, has shown that similar results can be obtained when G(n) is a convex or concave function. In this paper, we combine the ideas of Vaughan and Bateman to extend the theorems stated above to functions whose fractional differences are of one sign for large n. Vaughan's theorem is included in ours, and in the case $\text{β <}\text{k}\text{2}$ we show that a better choice of parameter improves Vaughan's result by enabling us to drop the power of log n from the estimate of the error term.     

Minimal rankings and the arank number of a path

Given a graph G, a function f:V(G)→{1,2,…,k} is a k-ranking of G if f(u)=f(v) implies every u-v path contains a vertex w such that f(w)>f(u). A k-ranking is minimal if the reduction of any label greater than 1 violates the described ranking property. The arank number of a graph, denoted ψ_r(G), is the largest k such that G has a minimal k-ranking. We present new results involving minimal k-rankings of paths. In particular, we determine ψ_r(P_n), a problem posed by Laskar and Pillone in 2000.