A multiplicative inequality for vertex Folkman numbers

Let G be a graph and a₁,…,a_r be positive integers. The symbol G→(a₁,…,a_r) denotes that in every r-coloring of the vertex set V(G) there exists a monochromatic a_i-clique of color i for some i∈{1,…,r}. The vertex Folkman numbers F(a₁,…,a_r;q)=min{|V(G)|:G→(a₁,…,a_r) and K_q?G} are considered. Let a_i, b_i, c_i, i∈{1,…,r}, s, t be positive integers and c_i=a_ib_i, 1?a_i?s,1?b_i?t. Then we prove that

F(c₁,c₂,…,c_r;st+1)?F(a₁,a₂,…,a_r;s+1)F(b₁,b₂,…,b_r;t+1).     

Bounds on some van der Waerden numbers

For positive integers s and k₁,k₂,…,ks, the van der Waerden number w(k₁,k₂,…,ks;s) is the minimum integer n such that for every s-coloring of set {1,2,…,n}, with colors 1,2,…,s, there is a ki-term arithmetic progression of color i for some i. We give an asymptotic lower bound for w(k,m;2) for fixed m. We include a table of values of w(k,3;2) that are very close to this lower bound for m=3. We also give a lower bound for w(k,k,…,k;s) that slightly improves previously-known bounds. Upper bounds for w(k,4;2) and w(4,4,…,4;s) are also provided.     

Davenport constant with weights and some related questions, II

Let G be a finite abelian group of order n and let A⊆Z be non-empty. Generalizing a well-known constant, we define the Davenport constant of G with weight A, denoted by DA(G), to be the least natural number k such that for any sequence (x₁,…,xk) with xi∈G, there exists a non-empty subsequence (xj₁,…,xjl) and a₁,…,al∈A such that . Similarly, for any such set A, EA(G) is defined to be the least t∈N such that for all sequences (x₁,…,xt) with xi∈G, there exist indices j₁,…,jn∈N,1?j₁<?<jn?t, and ?₁,…,?n∈A with . In the present paper, we establish a relation between the constants DA(G) and EA(G) under certain conditions. Our definitions are compatible with the previous generalizations for the particular group G=Z/nZ and the relation we establish had been conjectured in that particular case.     

Existence of positive solutions for 2nth-order singular sublinear boundary value problems

This paper investigates the existence of positive solutions for 2nth-order (n>1) singular sub-linear boundary value problems. A necessary and sufficient condition for the existence of C2n−2[0,1] as well as C2n−1[0,1] positive solutions is given by constructing lower and upper solutions and with the maximal theorem. Our nonlinearity f(t,x₁,x₂,…,xn) may be singular at xi=0, i=1,2,…,n, t=0 and/or t=1.     

Color-bounded hypergraphs, II: Interval hypergraphs and hypertrees

A color-bounded hypergraph is a hypergraph (set system) with vertex set X and edge set E={E₁,…,E_m}, together with integers s_i and t_i (1≤s_i≤t_i≤|E_i|) for i=1,…,m. A vertex coloring φ is feasible if the number of colors occurring in edge E_i satisfies s_i≤|φ(E_i)|≤t_i, for every i≤m.In this paper we point out that hypertrees-hypergraphs admitting a representation over a (graph) tree where each hyperedge E_i induces a subtree of the underlying tree-play a central role concerning the set of possible numbers of colors that can occur in feasible colorings. We also consider interval hypergraphs and circular hypergraphs, where the underlying graph is a path or a cycle, respectively. Sufficient conditions are given for a ‘gap-free’ chromatic spectrum; i.e., when each number of colors is feasible between minimum and maximum. The algorithmic complexity of colorability is studied, too.Compared with the ‘mixed hypergraphs’-where ‘D-edge’ means (s_i,t_i)=(2,|E_i|), while ‘C-edge’ assumes (s_i,t_i)=(1,|E_i|−1)-the differences are rather significant.     

Graham’s pebbling conjecture on product of thorn graphs of complete graphs

The pebbling number of a graph G, f(G), is the least n such that, no matter how n pebbles are placed on the vertices of G, we can move a pebble to any vertex by a sequence of pebbling moves, each move taking two pebbles off one vertex and placing one on an adjacent vertex. Let p₁,p₂,…,p_n be positive integers and G be such a graph, V(G)=n. The thorn graph of the graph G, with parameters p₁,p₂,…,p_n, is obtained by attaching p_i new vertices of degree 1 to the vertex u_i of the graph G, i=1,2,…,n. Graham conjectured that for any connected graphs G and H, f(G×H)≤f(G)f(H). We show that Graham’s conjecture holds true for a thorn graph of the complete graph with every by a graph with the two-pebbling property. As a corollary, Graham’s conjecture holds when G and H are the thorn graphs of the complete graphs with every .     

An Ore-type condition for arbitrarily vertex decomposable graphs

Let G be a graph of order n and r, 1≤r≤n, a fixed integer. G is said to be r-vertex decomposable if for each sequence (n₁,…,n_r) of positive integers such that n₁+?+n_r=n there exists a partition (V₁,…,V_r) of the vertex set of G such that for each i∈{1,…,r}, V_i induces a connected subgraph of G on n_i vertices. G is called arbitrarily vertex decomposable if it is r-vertex decomposable for each r∈{1,…,n}.In this paper we show that if G is a connected graph on n vertices with the independence number at most ⌈n/2⌉ and such that the degree sum of any pair of non-adjacent vertices is at least n−3, then G is arbitrarily vertex decomposable or isomorphic to one of two exceptional graphs. We also exhibit the integers r for which the graphs verifying the above degree-sum condition are not r-vertex decomposable.     

An asymptotic solution to the cycle decomposition problem for complete graphs

Let m₁,m₂,…,mt be a list of integers. It is shown that there exists an integer N such that for all n?N, the complete graph of order n can be decomposed into edge-disjoint cycles of lengths m₁,m₂,…,mt if and only if n is odd, 3?mi?n for i=1,2,…,t, and . In 1981, Alspach conjectured that this result holds for all n, and that a corresponding result also holds for decompositions of complete graphs of even order into cycles and a perfect matching.     

Distance distributions for graphs modeling computer networks

The Wiener polynomial of a graph G is a generating function for the distance distribution dd(G)=(D₁,D₂,…,D_t), where D_i is the number of unordered pairs of distinct vertices at distance i from one another and t is the diameter of G. We use the Wiener polynomial and several related generating functions to obtain generating functions for distance distributions of unweighted and weighted graphs that model certain large classes of computer networks. These provide a straightforward means of computing distance and timing statistics when designing new networks or enlarging existing networks.     

Operator norm localization property of relative hyperbolic group and graph of groups

In this article we study the spaces which have operator norm localization property. We prove that a finitely generated group Γ which is strongly hyperbolic with respect to a collection of finitely generated subgroups {H₁,…,Hn} has operator norm localization property if and only if each Hi, i=1,2,…,n, has operator norm localization property. Furthermore we prove the following result. Let π be the fundamental group of a connected finite graph of groups with finitely generated vertex groups GP. If GP has operator norm localization property for all vertices P then π has operator norm localization property.     

Perturbing non-real eigenvalues of non-negative real matrices

Let σ=(ρ,b+ic,b-ic,λ₄,…,λ_n) be the spectrum of an entry non-negative matrix and t?0. Laffey [T. J. Laffey, Perturbing non-real eigenvalues of nonnegative real matrices, Electron. J. Linear Algebra 12 (2005) 73-76] has shown that σ=(ρ+2t,b-t+ic,b-t-ic,λ₄,…,λ_n) is also the spectrum of some nonnegative matrix. Laffey (2005) has used a rank one perturbation for small t and then used a compactness argument to extend the result to all nonnegative t. In this paper, a rank two perturbation is used to deduce an explicit and constructive proof for all t?0.     

On some three color Ramsey numbers for paths and cycles

For given graphs G₁,G₂,…,G_k, k≥2, the multicolor Ramsey number, denoted by R(G₁,G₂,…,G_k), is the smallest integer n such that if we arbitrarily color the edges of a complete graph on n vertices with k colors, there is always a monochromatic copy of G_i colored with i, for some 1≤i≤k. Let P_k (resp. C_k) be the path (resp. cycle) on k vertices. In the paper we consider the value for numbers of type R(P_i,P_k,C_m) for odd m, k≥m≥3 and when i is odd, and when i is even. In addition, we provide the exact values for Ramsey numbers R(P₃,P_k,C₄) for all integers k≥3.     

New upper bounds for Estrada index of bipartite graphs

Suppose G is a graph and λ₁,λ₂,…,λ_n are the eigenvalues of G. The Estrada index EE(G) of G is defined as the sum of e^λ_i, 1≤i≤n. In this paper some new upper bounds for the Estrada index of bipartite graphs are presented. We apply our result on a (4,6)-fullerene to improve our bound given in an earlier paper.     

Bandwidth theorem for random graphs

A graph G is said to have bandwidth at most b, if there exists a labeling of the vertices by 1,2,…,n, so that |i−j|?b whenever {i,j} is an edge of G. Recently, Böttcher, Schacht, and Taraz verified a conjecture of Bollobás and Komlós which says that for every positive r, Δ, γ, there exists β such that if H is an n-vertex r-chromatic graph with maximum degree at most Δ which has bandwidth at most βn, then any graph G on n vertices with minimum degree at least (1−1/r+γ)n contains a copy of H for large enough n. In this paper, we extend this theorem to dense random graphs. For bipartite H, this answers an open question of Böttcher, Kohayakawa, and Taraz. It appears that for non-bipartite H the direct extension is not possible, and one needs in addition that some vertices of H have independent neighborhoods. We also obtain an asymptotically tight bound for the maximum number of vertex disjoint copies of a fixed r-chromatic graph H₀ which one can find in a spanning subgraph of G(n,p) with minimum degree (1−1/r+γ)np.     

The irredundant ramsey number s(3,3,3) = 13

Let G₁, G₂,. …, G_t be an arbitrary t-edge coloring of K_n, where for each i ∈ {1,2, …, t}, G_i is the spanning subgraph of K_n consisting of all edges colored with the ith color. The irredundant Ramsey number s(q₁, q₂, …, q_t) is defined as the smallest integer n such that for any t-edge coloring of K_n, _i has an irredundant set of size q_i for at least one i ∈ {1,2, …,t}. It is proved that s(3,3,3) = 13, a result that improves the known bounds 12 ≤ s(3,3,3) ≤ 14.     

Partitions of a set satisfying certain set of conditions

In this paper we present a new combinatorial class enumerated by Catalan numbers. More precisely, we establish a bijection between the set of partitions π₁π₂?π_n of [n] such that π_i+1−π_i≤1 for all i=,1,2…,n−1, and the set of Dyck paths of semilength n. Moreover, we find an explicit formula for the generating function for the number of partitions π₁π₂?π_n of [n] such that either π_i+?−π_i≤1 for all i=1,2,…,n−?, or π_i+1−π_i≤m for all i=1,2,…,n−1.     

Recognizing graphs with fixed interval number is NP-complete

A t-interval representation of a graph expresses it as the intersection graph of a family of subsets of the real line. Each vertex is assigned a set consisting of at most t disjoint closed intervals, in such a way that vertices are adjacent if and only if some interval for one intersects some interval for the other. The interval number i(G) of a graph G is the smallest number t such that G has a t-representation. We prove that, for any fixed value of t with t≥2, determining whether i(G)≤t is NP-complete.     

On the 1-factors of n-connected graphs

L. W. Beineke and M. D. Plummer have recently proved [1] that every n-connected graph with a 1-factor has at least n different 1-factors. The main purpose of this paper is to prove that every n-connected graph with a 1-factor has at least as many as n(n − 2)(n − 4) … 4 · 2, (or: n(n − 2)(n − 4) … 5 · 3) 1-factors. The main lemma used is: if a 2-connected graph G has a 1-factor, then G contains a vertex V (and even two such vertices), such that each edge of G, incident to V, belongs to some 1-factor of G.     

Critically indecomposable graphs

An undirected graph G=(V,E) with a specific subset X⊂V is called X-critical if G and G(X), induced subgraph on X, are indecomposable but G(V−{w}) is decomposable for every w∈V−X. This is a generalization of critically indecomposable graphs studied by Schmerl and Trotter [J.H. Schmerl, W.T. Trotter, Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures, Discrete Mathematics 113 (1993) 191-205] and Bonizzoni [P. Bonizzoni, Primitive 2-structures with the (n−2)-property, Theoretical Computer Science 132 (1994) 151-178], who deal with the case where X is empty.We present several structural results for this class of graphs and show that in every X-critical graph the vertices of V−X can be partitioned into pairs (a₁,b₁),(a₂,b₂),…,(a_m,b_m) such that G(V−{a_j1,b_j1,…,a_jk,b_jk}) is also an X-critical graph for arbitrary set of indices {j₁,…,j_k}. These vertex pairs are called commutative elimination sequence. If G is an arbitrary indecomposable graph with an indecomposable induced subgraph G(X), then the above result establishes the existence of an indecomposability preserving sequence of vertex pairs (x₁,y₁),…,(x_t,y_t) such that x_i,y_i∈V−X. As an application of the commutative elimination sequence of an X-critical graph we present algorithms to extend a 3-coloring (similarly, 1-factor) of G(X) to entire G.