Graphic sequences with a realization containing a complete multipartite subgraph

A nonincreasing sequence of nonnegative integers π=(d₁,d₂,…,d_n) is graphic if there is a (simple) graph G of order n having degree sequence π. In this case, G is said to realizeπ. For a given graph H, a graphic sequence π is potentiallyH-graphic if there is some realization of π containing H as a (weak) subgraph. Let σ(π) denote the sum of the terms of π. For a graph H and n∈Z⁺, σ(H,n) is defined as the smallest even integer m so that every n-term graphic sequence π with σ(π)≥m is potentially H-graphic. Let denote the complete t partite graph such that each partite set has exactly s vertices. We show that and obtain the exact value of σ(K_j+K_s,s,n) for n sufficiently large. Consequently, we obtain the exact value of for n sufficiently large.     

A generalization of a conjecture due to Erd?s, Jacobson and Lehel

An r-graph is a loopless undirected graph in which no two vertices are joined by more than r edges. An r-complete graph on m+1 vertices, denoted by , is an r-graph on m+1 vertices in which each pair of vertices is joined by exactly r edges. A non-increasing sequence π=(d₁,d₂,…,d_n) of nonnegative integers is r-graphic if it is realizable by an r-graph on n vertices. Let be the smallest even integer such that each n-term r-graphic sequence with term sum of at least is realizable by an r-graph containing as a subgraph. In this paper, we determine the value of for sufficiently large n, which generalizes a conjecture due to Erd?s, Jacobson and Lehel.     

A Havel-Hakimi type procedure and a sufficient condition for a sequence to be potentially S r,s -graphic

The split graph K _r + $\overline {{K_s}} $ on r+s vertices is denoted by S _r,s . A non-increasing sequence π = (d ₁, d ₂, …, d _n ) of nonnegative integers is said to be potentially S _r,s -graphic if there exists a realization of π containing S _r,s as a subgraph. In this paper, we obtain a Havel-Hakimi type procedure and a simple sufficient condition for π to be potentially S _r,s -graphic. They are extensions of two theorems due to A.R.Rao (The clique number of a graph with given degree sequence, Graph Theory, Proc. Symp., Calcutta 1976, ISI Lect. Notes Series 4 (1979), 251–267 and An Erd?s-Gallai type result on the clique number of a realization of a degree sequence, unpublished).     

Graphic sequences and split graphs

The split graph K _rVK _s on r+s vertices is denoted by S _r,s. A graphic sequence π = (d ₁, d ₂, ···, d _n) is said to be potentially S _r,s-graphic if there is a realization of π containing S _r,s as a subgraph. In this paper, a simple sufficient condition for π to be potentially S _r,s-graphic is obtained, which extends an analogous condition for p to be potentially K _r+1-graphic due to Yin and Li (Discrete Math. 301 (2005) 218–227). As an application of this condition, we further determine the values of σ(S _r,s, n) for n ≥ 3r + 3s - 1.     

Sequences that omit a box (modulo 1)

Let be a strictly increasing sequence of real numbers satisfying(0.1)aj+1−aj?σ>0. For an open box I in [0,1d⁾, we write It is shown that the Hausdorff dimension of is d−1 whenever The case d=1 is due to Boshernitzan. The proof builds on his approach.Now let S₁,…,Sd be strictly increasing in N. Define to be the set of x in [0, 1) for which A sequence S is said to fulfill condition D(C) if it containsBr=[ur,vr]∩S for which vr−ur→∞ and1+vr−ur?C#(Br). Kaufman has shown that is countable whenever S₁,…,Sd fulfill condition D(C). Here it is shown that is finite under this hypothesis. An upper bound for is provided.     

Two remarks on the Burr–Erdős conjecture

The Ramsey number r(H) of a graph H is the minimum positive integer N such that every two-coloring of the edges of the complete graph K_N on N vertices contains a monochromatic copy of H. A graph H is d-degenerate if every subgraph of H has minimum degree at most d. Burr and Erdős in 1975 conjectured that for each positive integer d there is a constant c_d such that r(H)≤c_dn for every d-degenerate graph H on n vertices. We show that for such graphs , improving on an earlier bound of Kostochka and Sudakov. We also study Ramsey numbers of random graphs, showing that for d fixed, almost surely the random graph G(n,d/n) has Ramsey number linear in n. For random bipartite graphs, our proof gives nearly tight bounds.     

Spectra of lifted Ramanujan graphs

A random n-lift of a base-graph G is its cover graph H on the vertices [n]×V(G), where for each edge uv in G there is an independent uniform bijection π, and H has all edges of the form (i,u),(π(i),v). A main motivation for studying lifts is understanding Ramanujan graphs, and namely whether typical covers of such a graph are also Ramanujan.Let G be a graph with largest eigenvalue λ₁ and let ρ be the spectral radius of its universal cover. Friedman (2003) [12] proved that every “new” eigenvalue of a random lift of G is with high probability, and conjectured a bound of ρ+o(1), which would be tight by results of Lubotzky and Greenberg (1995) [15]. Linial and Puder (2010) [17] improved Friedman?s bound to . For d-regular graphs, where λ₁=d and , this translates to a bound of O(d2/3), compared to the conjectured .Here we analyze the spectrum of a random n-lift of a d-regular graph whose nontrivial eigenvalues are all at most λ in absolute value. We show that with high probability the absolute value of every nontrivial eigenvalue of the lift is . This result is tight up to a logarithmic factor, and for λ?d2/3−ε it substantially improves the above upper bounds of Friedman and of Linial and Puder. In particular, it implies that a typical n-lift of a Ramanujan graph is nearly Ramanujan.     

Remarks on sub-fractional Bessel processes

Let S = {(St1,···,Std )}t≥0 denote a d-dimensional sub-fractional Brownian motion with index H ≥ 1/2. In this paper we study some properties of the process X of the formwhere Rt = ((St1)2+···+(Std)2)~1/2 is the sub-fractional Bessel process.     

Co-degree density of hypergraphs

For an r-graph H, let C(H)=minSd(S), where the minimum is taken over all (r−1)-sets of vertices of H, and d(S) is the number of vertices v such that S∪{v} is an edge of H. Given a family F of r-graphs, the co-degree Turán number is the maximum of C(H) among all r-graphs H which contain no member of F as a subhypergraph. Define the co-degree density of a family F to be

     

On potentially <Emphasis Type="Italic">H</Emphasis>-graphic sequences

For given a graph H, a graphic sequence π = (d ₁, d ₂,..., d _n) is said to be potentially H-graphic if there is a realization of π containing H as a subgraph. In this paper, we characterize the potentially (K ₅ − e)-positive graphic sequences and give two simple necessary and sufficient conditions for a positive graphic sequence π to be potentially K ₅-graphic, where K _r is a complete graph on r vertices and K _r-e is a graph obtained from K _r by deleting one edge. Moreover, we also give a simple necessary and sufficient condition for a positive graphic sequence π to be potentially K ₆-graphic. Project supported by National Natural Science Foundation of China (No. 10401010).     

Boxicity of line graphs

The boxicity of a graph H, denoted by , is the minimum integer k such that H is an intersection graph of axis-parallel k-dimensional boxes in R^k. In this paper we show that for a line graph G of a multigraph, , where Δ(G) denotes the maximum degree of G. Since G is a line graph, Δ(G)≤2(χ(G)−1), where χ(G) denotes the chromatic number of G, and therefore, . For the d-dimensional hypercube Q_d, we prove that . The question of finding a nontrivial lower bound for was left open by Chandran and Sivadasan in [L. Sunil Chandran, Naveen Sivadasan, The cubicity of Hypercube Graphs. Discrete Mathematics 308 (23) (2008) 5795–5800].The above results are consequences of bounds that we obtain for the boxicity of a fully subdivided graph (a graph that can be obtained by subdividing every edge of a graph exactly once).     

Turán’s theorem inverted

In this note we complete an investigation started by Erd?s in 1963 that aims to find the strongest possible conclusion from the hypothesis of Turán’s theorem in extremal graph theory.Let be the complete r-partite graph with parts of sizes s₁≥2,s₂,…,s_r with an edge added to the first part. Letting t_r(n) be the number of edges of the r-partite Turán graph of order n, we prove that:For all r≥2 and all sufficiently small c>0, every graph of sufficiently large order n with t_r(n)+1 edges contains a .We also give a corresponding stability theorem and two supporting results of wider scope.     

Pósa-condition and nowhere-zero 3-flows

Let G be a simple graph on n vertices and π(G)=(d₁,d₂,…,d_n) be the degree sequence of G, where n≥3 and d₁≤d₂≤?≤d_n. The classical Pósa’s theorem states that if d_m≥m+1 for and d_m+1≥m+1 for n being odd and , then G is Hamiltonian, which implies that G admits a nowhere-zero 4-flow. In this paper, we further show that if G satisfies the Pósa-condition that d_m≥m+1 for and d_m+1≥m+1 for n being odd and , then G has no nowhere-zero 3-flow if and only if G is one of seven completely described graphs.     

Disjoint unions of complete minors

Given integers r and s, and n large compared to r and s, we determine the maximum size of a graph of order n having no minor isomorphic to sK_r, the union of s disjoint copies of K_r.The extremal function depends on the relative sizes of r and s. If s is small compared to r the extremal function is essentially independent of s. On the other hand, if s is large compared to r, there is a unique extremal graph ; this assertion is a generalization of the case r=3 which is a classical result of Erd?s and Pósa.     

A Liapunov type inequality for Sugeno integrals

The classical Liapunov inequality shows an interesting upper bound for the Lebesgue integral of the product of two functions. This paper proposes a Liapunov type inequality for Sugeno integrals. That is, we show that holds for some constant H_s,t,r where 0<t<s<r,f:[0,1]→[0,∞) is a non-increasing concave function, and μ is the Lebesgue measure on R. We also present two interesting classes of functions for which the classical Liapunov type inequality for Sugeno integrals with H_s,t,r=1 holds. Some examples are provided to illustrate the validity of the proposed inequality.     

The asymptotic number of spanning trees in circulant graphs

Let T(G) be the number of spanning trees in graph G. In this note, we explore the asymptotics of T(G) when G is a circulant graph with given jumps.The circulant graph is the 2k-regular graph with n vertices labeled 0,1,2,…,n−1, where node i has the 2k neighbors i±s₁,i±s₂,…,i±s_k where all the operations are . We give a closed formula for the asymptotic limit as a function of s₁,s₂,…,s_k. We then extend this by permitting some of the jumps to be linear functions of n, i.e., letting s_i, d_i and e_i be arbitrary integers, and examining

     

The upper connected geodetic number and forcing connected geodetic number of a graph

For a connected graph G of order p≥2, a set S⊆V(G) is a geodetic set of G if each vertex v∈V(G) lies on an x-y geodesic for some elements x and y in S. The minimum cardinality of a geodetic set of G is defined as the geodetic number of G, denoted by g(G). A geodetic set of cardinality g(G) is called a g-set of G. A connected geodetic set of G is a geodetic set S such that the subgraph G[S] induced by S is connected. The minimum cardinality of a connected geodetic set of G is the connected geodetic number of G and is denoted by g_c(G). A connected geodetic set of cardinality g_c(G) is called a g_c-set of G. A connected geodetic set S in a connected graph G is called a minimal connected geodetic set if no proper subset of S is a connected geodetic set of G. The upper connected geodetic number is the maximum cardinality of a minimal connected geodetic set of G. We determine bounds for and determine the same for some special classes of graphs. For positive integers r,d and n≥d+1 with r≤d≤2r, there exists a connected graph G with , and . Also, for any positive integers 2≤a<b≤c, there exists a connected graph G such that g(G)=a, g_c(G)=b and . A subset T of a g_c-set S is called a forcing subset for S if S is the unique g_c-set containing T. A forcing subset for S of minimum cardinality is a minimum forcing subset of S. The forcing connected geodetic number of S, denoted by f_c(S), is the cardinality of a minimum forcing subset of S. The forcing connected geodetic number of G, denoted by f_c(G), is f_c(G)=min{f_c(S)}, where the minimum is taken over all g_c-sets S in G. It is shown that for every pair a,b of integers with 0≤a≤b−4, there exists a connected graph G such that f_c(G)=a and g_c(G)=b.     

Domination of generalized Cartesian products

The generalized prism πG of G is the graph consisting of two copies of G, with edges between the copies determined by a permutation π acting on the vertices of G. We define a generalized Cartesian product that corresponds to the Cartesian product when π is the identity, and the generalized prism when H is the graph K₂. Burger, Mynhardt and Weakley [A.P. Burger, C.M. Mynhardt, W.D. Weakley, On the domination number of prisms of graphs, Discuss. Math. Graph Theory 24 (2) (2004) 303-318.] characterized universal doublers, i.e. graphs for which γ(πG)=2γ(G) for any π. In general for any n≥2 and permutation π, and a graph attaining equality in this upper bound for all π is called a universal multiplier. We characterize such graphs.     

Asymptotic Enumeration of Convex Polygons

A polygon is an elementary (self-avoiding) cycle in the hypercubic lattice ^dtaking at least one step in every dimension. A polygon on ^dis said to be convex if its length is exactly twice the sum of the side lengths of the smallest hypercube containing it. The number ofd-dimensional convex polygonsp_{n, d}of length 2nwithd(n)→∞ is asymptoticallywherer=r(n, d) is the unique solution ofr coth r=2n/d−1andb(r)=d(r coth r−r²/sinh² r). The convergence is uniform over alld?ω(n) for any functionω(n)→∞. Whendis constant the exponential is replaced with (1−d⁻¹)^2d. These results are proved by asymptotically enumerating a larger class of combinatorial objects calledconvex proto-polygonsby the saddle-point method and then finding the asymptotic probability a randomly chosen convex proto-polygon is a convex polygon.     

Distributing vertices along a Hamiltonian cycle in Dirac graphs

A graph G on n vertices is called a Dirac graph if it has a minimum degree of at least n/2. The distance is defined as the number of edges in a shortest path of G joining u and v. In this paper we show that in a Dirac graph G, for every small enough subset S of the vertices, we can distribute the vertices of S along a Hamiltonian cycle C of G in such a way that all but two pairs of subsequent vertices of S have prescribed distances (apart from a difference of at most 1) along C. More precisely we show the following. There are ω,n₀>0 such that if G is a Dirac graph on n≥n₀ vertices, d is an arbitrary integer with 3≤d≤ωn/2 and S is an arbitrary subset of the vertices of G with 2≤|S|=k≤ωn/d, then for every sequence d_i of integers with 3≤d_i≤d,1≤i≤k−1, there is a Hamiltonian cycle C of G and an ordering of the vertices of S, a₁,a₂,…,a_k, such that the vertices of S are visited in this order on C and we have