A Note on Uniquely lntersectable Graphs

The following conjecture of Alter and Wang is proven. Consider the intersection graph G_n,m,n?2m, determined by the family of all m-element subsets of an n-element set. Then any realization of G_n,m as an intersection graph by a family of sets satisfies |∪_iA_i|?n; and if |∪_iA_i|=n, then F must be the family of all m-element subsets of ∪_iA_i.     

Ore‐type degree conditions for a graph to be H‐linked

Given a fixed multigraph H with V(H) = {h₁,…, h_m}, we say that a graph G is H‐linked if for every choice of m vertices v₁, …, _vm in G, there exists a subdivision of H in G such that for every i, v_i is the branch vertex representing h_i. This generalizes the notion of k‐linked graphs (as well as some other notions). For a family of graphs, a graph G is ‐linked if G is H‐linked for every . In this article, we estimate the minimum integer r = r(n, k, d) such that each n‐vertex graph with is ‐linked, where is the family of simple graphs with k edges and minimum degree at least . © 2008 Wiley Periodicals, Inc. J Graph Theory 58: 14–26, 2008     

Globally sparse vertex-ramsey graphs

For graphs G and F we write F → (G)¹_r if every r-coloring of the vertices of F results in a monochromatic copy of G. The global density m(F) of F is the maximum ratio of the number of edges to the number of vertices taken over all subgraphs of F. Let We show that The lower bound is achieved by complete graphs, whereas, for all r ≥ 2 and ? > 0, m_cr(S_k, r) > r - ? for sufficiently large k, where S_k is the star with k arms. In particular, we prove that      

On the domination of the products of graphs II: Trees

For a graph G, a subset of vertices D is a dominating set if for each vertex X not in D, X is adjacent to at least one vertex of D. The domination number, γ(G), is the order of the smallest such set. An outstanding conjecture in the theory of domination is for any two graph G and H, One result presented in this paper settles this question in the case when at least one of G or H is a tree. We show that for all graphs G and any tree T. Furthermore, we supply a partial characterization for which pairs of trees, T₁ and T₂, strict inequality occurs. We show for almost all pairs of trees.     

Non-local Dirichlet forms generated by pseudodifferential operators on compact abelian groups

Let G_i, 1 ≤ i ≤ n, be compact abelian groups and let Γ_i , 1 ≤ i ≤ n, be countable dual groups. We consider G = G₁ ⊕ G₂ ⊕ … ⊕ G_n and Γ = Γ₁ ⊕ Γ₂ ⊕ … ⊕ Γ_n . For 1 ≤ j ≤ n, let a_j be a negative definite function on Γ_j and a (γ) = . For φ ∈ S (G), the set of all generalized trigonometrical polynomials on G, we define , where (γ) = a_j (γ_j) (γ), 1 ≤ j ≤ n. Then is a Dirichlet form with the domain on L² (G). (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

The Ramsey numbers for disjoint unions of graphs

For given graphs G and H, the Ramsey number R(G,H) is the smallest natural number n such that for every graph F of order n: either F contains G or the complement of F contains H. In this paper we investigate the Ramsey number of a disjoint union of graphs . For any natural integer k, we contain a general upper bound, R(kG,H)?R(G,H)+(k-1)|V(G)|. We also show that if m=2n-4, 2n-8 or 2n-6, then R(kS_n,W_m)=R(S_n,W_m)+(k-1)n. Furthermore, if |G_i|>(|G_i|-|G_i+1|)(χ(H)-1) and R(G_i,H)=(χ(H)-1)(|G_i|-1)+1, for each i, then .     

Two‐factors each component of which contains a specified vertex

It is shown that if G is a graph of order n with minimum degree δ(G), then for any set of k specified vertices {v₁,v₂,…,v_k} ? V(G), there is a 2‐factor of G with precisely k cycles {C₁,C₂,…,C_k} such that v_i ∈ V(C_i) for (1 ≤ i ≤ k) if or 3k + 1 ≤ n ≤ 4k, or 4k ≤ n ≤ 6k ? 3,δ(G) ≥ 3k ? 1 or n ≥ 6k ? 3, . Examples are described that indicate this result is sharp. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 188–198, 2003     

On the irregularity strength of trees

For any graph G, let n_i be the number of vertices of degree i, and . This is a general lower bound on the irregularity strength of graph G. All known facts suggest that for connected graphs, this is the actual irregularity strength up to an additive constant. In fact, this was conjectured to be the truth for regular graphs and for trees. Here we find an infinite sequence of trees with λ(T) = n₁ but strength converging to . © 2004 Wiley Periodicals, Inc. J Graph Theory 45: 241–254, 2004     

Graph Decompositions Satisfying Extremal Degree Constraints

We show that the vertex set of any graph G with p?2 vertices can be partitioned into non-empty sets V₁, V₂, such that the maximum degree of the induced subgraph 〈V_i〉 does not exceed where pⁱ = |Vⁱ|, for i=1, 2. Furthermore, the structure of the induced subgraphs is investigated in the extreme case.     

A sharp edge bound on the interval number of a graph

The interval number of a graph G, denoted by i(G), is the least natural number t such that G is the intersection graph of sets, each of which is the union of at most t intervals. Here we settle a conjecture of Griggs and West about bounding i(G) in terms of e, that is, the number of edges in G. Namely, it is shown that i(G) ≤ + 1. It is also observed that the edge bound induces i(G) ≤ , where γ(G) is the genus of G. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 153–159, 1999     

Nullstellensatz effectif et Conjecture de Serre (Théorème de Quillen-Suslin) pour le Calcul Formel

Let k be an arbitrary field, X₁,….,X_n indeterminates over k and F₁…, F₃ ε ∈ k[X₁…,X_n] polynomials of maximal degree $ d: = \mathop {\max }\limits_{1 \le i \le a} \deg $ (F_i). We give an elementary proof of the following effective Nullstellensatz: Assume that F₁,…,F have no common zero in the algebraic closure of k. Then there exist polynomials P₁…, P₃ ε ∈ k[X₁…,X_n] such that $ 1: = \mathop \Sigma \limits_{1 \le i \le a} $ P_iF_i and This result has many applications in Computer Algebra. To exemplify this, we give an effective quantitative and algorithmic version of the Quillen-Suslin Theorem baaed on our effective Nullstellensatz.     

Extending an edge-coloring

When can a k-edge-coloring of a subgraph K of a graph G be extended to a k-edge-coloring of G? One necessary condition is that for all X ? E(G) - E(K), where μ_i(X) is the maximum cardinality of a subset of X whose union with the set of edges of K colored i is a matching. This condition is not sufficient in general, but is sufficient for graphs of very simple structure. We try to locate the border where sufficiency ends.     

Characterization of edge‐colored complete graphs with properly colored Hamilton paths

An edge‐colored graph H is properly colored if no two adjacent edges of H have the same color. In 1997, J. Bang‐Jensen and G. Gutin conjectured that an edge‐colored complete graph G has a properly colored Hamilton path if and only if G has a spanning subgraph consisting of a properly colored path C₀ and a (possibly empty) collection of properly colored cycles C₁,C₂,…, C_d such that provided . We prove this conjecture. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 333–346, 2006     

Asymptotic behavior of the solutions of certain parabolic equations

Some laws in physics describe the change of a flux and are represented by parabolic equations of the form (*) \documentclass{article}\pagestyle{empty}\begin{document}$$\frac{{\partial u}}{{\partial t}}=\frac{\partial}{{\partial x_j }}(\eta \frac{{\partial u}}{{ax_j}}-vju),$$\end{document} j≤m, where η and v_j are functions of both space and time. We show under quite general assumptions that the solutions of equation (*) with homogeneous Dirichlet boundary conditions and initial condition u(x, 0) = u_o(x) satisfy The decay rate d > 0 only depends on bounds for η, v and G § R^m the spatial domain, while the constant c depends additionally on which norm is considered. For the solutions of equation (*) with homogeneous Neumann boundary conditions and initial condition u₀(x) ≥ 0 we derive bounds d₁u₁ ≤ u(x, t) ≤ d₂u₂, Where d_i, i = 1, 2, depend on bounds for η, v and G, and the u_i are bounds on the initial condition u₀.     

The circular chromatic number of the Mycielskian of G

In a search for triangle-free graphs with arbitrarily large chromatic numbers, Mycielski developed a graph transformation that transforms a graph G into a new graph μ(G), we now call the Mycielskian of G, which has the same clique number as G and whose chromatic number equals χ(G) + 1. Chang, Huang, and Zhu [G. J. Chang, L. Huang, & X. Zhu, Discrete Math, to appear] have investigated circular chromatic numbers of Mycielskians for several classes of graphs. In this article, we study circular chromatic numbers of Mycielskians for another class of graphs G. The main result is that χ_c(μ(G)) = χ(μ(G)), which settles a problem raised in [G. J. Chang, L. Huang, & X. Zhu, Discrete Math, to appear, and X. Zhu, to appear]. As χ_c(G) = and χ(G) = , consequently, there exist graphs G such that χ_c(G) is as close to χ(G) − 1 as you want, but χ_c(μ(G)) = χ(μ(G)). © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 63–71, 1999     

Total relative displacement of vertex permutations of K

Let α denote a permutation of the n vertices of a connected graph G. Define δ_α(G) to be the number , where the sum is over all the unordered pairs of distinct vertices of G. The number δ_α(G) is called the total relative displacement of α (in G). So, permutation α is an automorphism of G if and only if δ_α(G) = 0. Let π(G) denote the smallest positive value of δ_α(G) among the n! permutations α of the vertices of G. A permutation α for which π(G) = δ_α(G) has been called a near‐automorphism of G [ 2 ]. We determine π(K) and describe permutations α of K for which π(K) = δ_α(K). This is done by transforming the problem into the combinatorial optimization problem of maximizing the sums of the squares of the entries in certain t by t matrices with non–negative integer entries in which the sum of the entries in the ith row and the sum of the entries in the ith column each equal to n_i,1≤i≤t. We prove that for positive integers, n₁≤n₂≤…≤n_t, where t≥2 and n_t≥2, where k₀ is the smallest index for which n = n+1. As a special case, we correct the value of π(K_m,n), for all m and n at least 2, given by Chartrand, Gavlas, and VanderJagt [ 2 ]. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 85–100, 2002     

Hamiltonian cycles in 2-connected claw-free-graphs

M. Matthews and D. Sumner have proved that of G is a 2-connected claw-free graph of order n such that δ ≧ (n ? 2)/3, then G is hamiltonian. We prove that the bound for the minimum degree δ can be reduced to n/4 under the additional condition that G is not in F, where F is the set of all graphs defined as follows: any graph H in F can be decomposed into three vertex disjoint subgraphs H₁, H₂, H₃ such that , where u_i, v_i ? V(H_i), u_j v_j ? V(H_j) 1 ? i ≦ j ≦ 3. Examples are given to show that the bound n/4 is sharp. © 1995 John Wiley & Sons, Inc.     

On series of signed vectors and their rearrangements

Let x₁,…,x_m∈ \input amssym $ \Bbb R$ n be a sequence of vectors with ∥x_i∥₂ ≤ 1 for all i. It is proved that there are signs ε₁,…,ε_m = ±1 such that where C₁, C₂ are some numerical constants. It is also proved that there are signs ε,…,ε = ±1 and a permutation π of {1,…,m} such that where C^′ is some other numerical constant. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

Relative difference sets in semidirect products with an amalgamated subgroup

We call a group G with subgroups G₁, G₂ such that G = G₁G₂ and both N = G₁ ∩ G₂ and G₁ are normal in G a semidirect product with amalgamated subgroup N. We show that if G_l is a group with N_l ? G_l containing a relative ‐difference set relative to N_l for l = 1,2, and if there exists a “compatible coupling” from (G₂, N₂) to (G₁, N₁), a notion introduced in the paper, then for any i,j ∈ ? there exists at least one semidirect product with amalgamated subgroup N ? N₁ ? N₂ containing a relative ‐difference set. We say “at least one” to emphasize that the proof is via recursive construction and that different groups may be obtained depending on the choices made at different stages of the recursion. A special case of this result shows that if K is any finite group containing a normal relative ‐difference set, then there exists, for each i ∈ ?, at least one semidirect product with amalgamated subgroup N containing a relative ‐difference set. These results suggest that the class of semidirect products with an amalgamated subgroup provides a rich source of new (non‐abelian) semiregular relative difference sets. © 2004 Wiley Periodicals, Inc.