Signed 2-independence in graphs

A function f : V→{−1,1} defined on the vertices of a graph G=(V,E) is a signed 2-independence function if the sum of its function values over any closed neighbourhood is at most one. That is, for every vV, f(N[v])1, where N[v] consists of v and every vertex adjacent to v. The weight of a signed 2-independence function is f(V)=∑f(v), over all vertices vV. The signed 2-independence number of a graph G, denoted α_s²(G), equals the maximum weight of a signed 2-independence function of G. In this paper, we establish upper bounds for α_s²(G) in terms of the order and size of the graph, and we characterize the graphs attaining these bounds. For a tree T, upper and lower bounds for α_s²(T) are established and the extremal graphs characterized. It is shown that α_s²(G) can be arbitrarily large negative even for a cubic graph G.     

Existence of maximal solutions

Let Ω be a plane bounded region. Let U = {U_μ(P):μ(P)εL∞(Ω), u_μ ε H²_{2, 0}(Ω) and a(P, μ(P))u_μ,xx + 2b(P, μ(P))u_μ,xy + c(P, μ(P))u_μ,vv = ƒ(P) for P ε Ω; here we are given a(P, X), b(P, X), c(P, X) ε L_∞(Ω × E¹), ƒ(P) ε L_p(Ω) with p > 2, and our partial differential equation is uniformly elliptic. The functions μ(P) are called profiles. We establish sufficient conditions—which when they apply are constructive—that there exist a μ₀ ε L_∞(Ω) such that u_μ0 (P) u_μ(P) for all P ε Ω and for each μ ε L_∞(Ω). Similar results are obtained for a difference equation and convergence is proved.     

On the degree of weak convergence of a sequence of finite measures to the unit measure under convexity

This is a study of the degree of weak convergence under convexity of a sequence of finite measures μ_j on ^k, k 1, to the unit measure δ_x0. LetQ denote a convex and compact subset of ^k, let ƒ ε C^m(Q), m 0, satisfy a convexity condition and let μ be a finite measure on Q. Using standard moment methods, upper bounds and best upper bounds are obtained for ¦∝_Qƒdμ − ƒ(x₀)¦. They sometimes lead to sharp inequalities which are attained for particular μ and ƒ. These estimates are better than the corresponding ones found in the literature.     

The structure of the algebraic eigenspace to the spectral radius of eventually compact, nonnegative integral operators

Let K be an eventually compact linear integral operator on L^p(Ω, μ), 1 p < ∞, with nonnegative kernel k(x, y), where the underlying measure μ is totally σ-finite on the domain set Ω when P = 1. This work extends the previous analysis of the author who characterized the distinguished eigenvalues of K and K^*, and the support sets for the eigenfunctions and generalized eigenfunctions belonging to the spectral radius of K or K^*. The characterizations of the support sets for the algebraic eigenspaces of K or K^* are phrased in terms of significant k-components which are maximal irreducible subsets of Ω and which yield a positive spectral radius for the integral operator defined by the restriction of k(x, y) to the Cartesian product of such sets. In this paper, we show that a basis for the functions, constituting the algebraic eigenspaces of K and K^* belonging to the spectral radius of K, can be chosen to consist of elements which are positive on their sets of support, except possibly on sets of measure less than some arbitrarily specified positive number. In addition, we present necessary and sufficient conditions, in terms of the significant k-components, for both K and K^* to possess a positive eigenfunction (a.e. μ) corresponding to the spectral radius, as well as necessary and sufficient conditions for the sequence γⁿKⁿg _p to converge whenever g 0, where − _p denotes the norm in L^p(Ω, μ), and γ₁ the smallest (in modulus) characteristic value of K. This analysis is made possible by introducing the concepts of chains, lengths of chains, height, and depth of a significant k-component as was done by U. Rothblum [Lin. Alg. Appl. 12 (1975), 281–292] for the matrix setting.     

Bounded edge-connectivity and edge-persistence of Cartesian product of graphs

The bounded edge-connectivity λ_k(G) of a connected graph G with respect to is the minimum number of edges in G whose deletion from G results in a subgraph with diameter larger than k and the edge-persistence D⁺(G) is defined as λ_d(G)(G), where d(G) is the diameter of G. This paper considers the Cartesian product G₁×G₂, shows λ_k1+k2(G₁×G₂)≥λ_k1(G₁)+λ_k2(G₂) for k₁≥2 and k₂≥2, and determines the exact values of D⁺(G) for G=C_n×P_m, C_n×C_m, Q_n×P_m and Q_n×C_m.     

More on Ordinary Differential Equations Which Yield Periodic Solutions of Delay Differential Equations

We construct a Poincaré operator for the system where λ is a real parameter, x ³, x = (x₁, x₂, x₃), [formula], and ƒ is an odd C² function such that ƒ′(0) = 1, xƒ(x) > 0, for x ≠ 0. We also consider the case where ƒ is C¹. We will express F in linearized form, that is, F(x) = Ax + G(x), where A is the linearized part of F around zero and G(x) = o(|x|) near zero. Fixed points of the Poincaré operator correspond to periodic solutions of the functional differential equation

Full-size image

where T is the period of x.     

Schur functions and the invariant polynomials characterizing U(n) tensor operators

We give a direct formulation of the invariant polynomials _μG_q⁽ⁿ⁾(, Δ_i,;, x_{i,i + 1},) characterizing U(n) tensor operators p, q, …, q, 0, …, 0 in terms of the symmetric functions S_λ known as Schur functions. To this end, we show after the change of variables Δ_i = γ_i − δ_i and x_{i, i + 1} = δ_i − δ_{i + 1} that_μG_q⁽ⁿ⁾(,Δ_i;, x_{i, i + 1},) becomes an integral linear combination of products of Schur functions S_α(, γ_i,) · S_β(, δ_i,) in the variables {γ₁,…, γ_n} and {δ₁,…, δ_n}, respectively. That is, we give a direct proof that _μG_q⁽ⁿ⁾(,Δ_i,;, x_{i, i + 1},) is a bisymmetric polynomial with integer coefficients in the variables {γ₁,…, γ_n} and {δ₁,…, δ_n}. By making further use of basic properties of Schur functions such as the Littlewood-Richardson rule, we prove several remarkable new symmetries for the yet more general bisymmetric polynomials _μ^mG_q⁽ⁿ⁾(γ₁,…, γ_n; δ₁,…, δ_m). These new symmetries enable us to give an explicit formula for both _μ^mG₁⁽ⁿ⁾(γ; δ) and ₁G₂⁽ⁿ⁾(γ; δ). In addition, we describe both algebraic and numerical integration methods for deriving general polynomial formulas for _μ^mG_q⁽ⁿ⁾(γ; δ).     

Matrices dont deux lignes quelconque coïncident dans un nombre donne de positions communes

Le nombre maximal de lignes de matrices seront désignées par:

1. (a) R(k, λ) si chaque ligne est une permutation de nombres 1, 2,…, k et si chaque deux lignes différentes coïncide selon λ positions;

2. (b) S⁰(k, λ) si le nombre de colonnes est k et si chaque deux lignes différentes coïncide selon λ positions et si, en plus, il existe une colonne avec les éléments y₁, y₂, y₃, ou y₁ = y₂ ≠ y₃;

3. (c) T⁰(k, λ) si c'est une (0, 1)-matrice et si chaque ligne contient k unités et si chaque deux lignes différentes contient les unités selon λ positions et si, en plus, il existe une colonne avec les éléments 1, 1, 0.

La fonction T⁰(k, λ) était introduite par Chvátal et dans les articles de Deza, Mullin, van Lint, Vanstone, on montrait que T⁰(k, λ) max(λ + 2, (k − λ)² + k − λ + 1). La fonction S⁰(k, λ) est introduite ici et dans le Théorème 1 elle est étudiée analogiquement; dans les remarques 4, 5, 6, 7 on donne les généralisations de problèmes concernant T⁰(k, λ), S⁰(k, λ), dans la remarque 9 on généralise le problème concernant R(k, λ). La fonction R(k, λ) était introduite et étudiée par Bolton. Ci-après, on montre que R(k, λ) S⁰(k, λ) T⁰(k, λ) d'où découle en particulier: R(k, λ) λ + 2 pour λ k + 1 − (k + 2)^1/2; R(k, λ) = 0(k²) pour k − λ = 0(k); R(k, λ) (k − 1)² − (k + 2) pour k 1191.     

Absolute continuity of information channels

Let [X, v, Y] be an abstract information channel with the input X = (X, ) and the output Y = (Y, ) which are measurable spaces, and denote by L(Y) = L(Y, ) the Banach space of all bounded signed measures with finite total variation as norm. The channel distribution ν(·,·) is considered as a function defined on (X, ) and valued in L(Y). It will be proved that, if the measurable space (Y, ) is countably generated, then the is a strongly measurable function from X into L(Y) if and only if there exists a probability measure μ on (Y, ) which dominates every measure ν(x, ·) (x X). Furthermore, under this condition, the Radon-Nikodym derivative ν(x, dy)/μ(dy) is jointly measurable with respect to the product measure space (X, , m) (Y, , μ) where m is any but fixed probability measure of (X, ). As an application, it will be shown that the channel given as above is uniformly approximated by channels of Hibert-Schmidt type.     

The Pointwise Densities of the Cantor Measure

Let be the classical middle-third Cantor set and let μ be the Cantor measure. Set s = log 2/log 3. We will determine by an explicit formula for every point x the upper and lower s-densities Θ*^s(μ , x), Θ*^s(μ , x) of the Cantor measure at the point x, in terms of the 3-adic expansion of x. We show that there exists a countable set F such that 9(Θ*^s(μ , x))^{− 1/s} + (Θ*^s(μ , x))^{− 1/s} = 16 holds for x \F. Furthermore, for μ_C almost all x, Θ*^s(μ , X) − 2 · 4^{− s} and Θ*^s(μ , x) = 4^{− s}. As an application, we will show that the s-dimensional packing measure of the middle-third Cantor set is 4^s.     

On the number of cycles of length k in a maximal planar graph

Let G be a maximal planar graph with p vertices, and let C_k(G) denote the number of cycles of length k in G. We first present tight bounds for C₃(G) and C₄(G) in terms of p. We then give bounds for C_k(G) when 5 ≤ k ≤ p, and consider in particular bounds for C_p(G), in terms of p. Some conjectures and unsolved problems are stated.     

Structures and Chromaticity of Extremal 3-Colourable Sparse Graphs

 Assume that G is a 3-colourable connected graph with e(G) = 2v(G) −k, where k≥ 4. It has been shown that s ₃(G) ≥ 2 ^{k −3}, where s _r (G) = P(G,r)/r! for any positive integer r and P(G, λ) is the chromatic polynomial of G. In this paper, we prove that if G is 2-connected and s ₃(G) < 2 ^{k −2}, then G contains at most v(G) −k triangles; and the upper bound is attained only if G is a graph obtained by replacing each edge in the k-cycle C _k by a 2-tree. By using this result, we settle the problem of determining if W(n, s) is χ-unique, where W(n, s) is the graph obtained from the wheel W _n by deleting all but s consecutive spokes. Received: January 29, 1999 Final version received: April 8, 2000     

Posets and planar graphs

A k-decomposition (G₁,…,G_k) of a graph G is a partition of its edge set to form k spanning subgraphs G₁,…,G_k. The classical theorem of Nordhaus and Gaddum bounds χ(G₁) + χ(G₂) and χ(G₁)χ(G₂) over all 2-decompositions of K_n. For a graph parameter p, let p(k;G) denote the maximum of over all k-decompositions of the graph G. The clique number ω, chromatic number χ, list chromatic number χℓ, and Szekeres–Wilf number σ satisfy ω(2;K_n) = χ(2;K_n) = χℓ(2;K_n) = σ(2;K_n) = n + 1. We obtain lower and upper bounds for ω(k;K_n), χ(k;K_n), χℓ(k;K_n), and σ(k;K_n). The last three behave differently for large k. We also obtain lower and upper bounds for the maximum of χ(k;G) over all graphs embedded on a given surface. © 2005 Wiley Periodicals, Inc. J Graph Theory     

A 2-factor with Short Cycles Passing Through Specified Independent Vertices in Graph

For a graph G, we define σ₂(G) := min{d(u) + d(v)|u, v ≠ ∈ E(G), u ≠ v}. Let k ≥ 1 be an integer and G be a graph of order n ≥ 3k. We prove if σ₂(G) ≥ n + k − 1, then for any set of k independent vertices v ₁,...,v _k , G has k vertex-disjoint cycles C ₁,..., C _k of length at most four such that v _i ∈ V(C _i ) for all 1 ≤ i ≤ k. And show if σ₂(G) ≥ n + k − 1, then for any set of k independent vertices v ₁,...,v _k , G has k vertex-disjoint cycles C ₁,..., C _k such that v _i ∈ V(C _i ) for all 1 ≤ i ≤ k, V(C ₁) ∪...∪ V(C _k ) = V(G), and |C _i | ≤ 4 for all 1 ≤ i ≤ k − 1. The condition of degree sum σ₂(G) ≥ n + k − 1 is sharp. Received: December 20, 2006. Final version received: December 12, 2007.     

A generalization of Burnside's combinatorial lemma

Let G be a finite group which acts on a set S. We present a method of computing the entire distribution of G-orbits of S (the number of k-element G-orbits of S for all k) in terms of the number of s ε S fixed by every σ ε H for subgroups H of G, and the Möbius function μ(·, ·) defined on the subgroup lattice of G. We deduce Burnside's lemma as a consequence of our result.     

Centers to centroids in graphs

For S ? V(G) the S-center and S-centroid of G are defined as the collection of vertices u ∈ V(G) that minimize e_s(u) = max {d(u, v): v ∈ S} and d_s(u) = ∑_u∈S d(u, v), respectively. This generalizes the standard definition of center and centroid from the special case of S = V(G). For 1 ? k ?|V(G)| and u ∈ V(G) let r_k(u) = max {∑_s∈S d(u, s): S ? V(G), |S| = k}. The k-centrum of G, denoted C(G; k), is defined to be the subset of vertices u in G for which r_k(u) is a minimum. This also generalizes the standard definitions of center and centroid since C(G; 1) is the center and C(G; |V(G)|) is the centroid. In this paper the structure of these sets for trees is examined. Generalizations of theorems of Jordan and Zelinka are included.     

On the locating chromatic number of Kneser graphs

Let c be a proper k-coloring of a connected graph G and Π=(C₁,C₂,…,C_k) be an ordered partition of V(G) into the resulting color classes. For a vertex v of G, the color code of v with respect to Π is defined to be the ordered k-tuple c_Π(v):=(d(v,C₁),d(v,C₂),…,d(v,C_k)), where d(v,C_i)=min{d(v,x)|x∈C_i},1≤i≤k. If distinct vertices have distinct color codes, then c is called a locating coloring. The minimum number of colors needed in a locating coloring of G is the locating chromatic number of G, denoted by χ_L(G). In this paper, we study the locating chromatic number of Kneser graphs. First, among some other results, we show that χ_L(KG(n,2))=n−1 for all n≥5. Then, we prove that χ_L(KG(n,k))≤n−1, when n≥k². Moreover, we present some bounds for the locating chromatic number of odd graphs.     

A note on traversing specified vertices in graphs embedded with large representativity

A graph G is said to have property P(2,k) if given any k+2 distinct vertices a,b,v₁,…,v_k, there is a path P in G joining a and b and passing through all of v₁,…,v_k. A graph G is said to have property C(k) if given any k distinct vertices v₁,…,v_k, there is a cycle C in G containing all of v₁,…,v_k. It is shown that if a 4-connected graph G is embedded in an orientable surface Σ (other than the sphere) of Euler genus eg(G,Σ), with sufficiently large representativity (as a function of both eg(G,Σ) and k), then G possesses both properties P(2,k) and C(k).     

Semiharmonic trees and monocyclic graphs

A graph G is defined to be semiharmonic if there is a constant μ (necessarily a natural number) such that, for every vertex v, the number of walks of length 3 starting in v equals μd_G(v) where d_G(v) is the degree of v. We determine all finite semiharmonic trees and monocyclic graphs.     

Representations for the first associated q-classical orthogonal polynomials

Let {p_k(x; q)} be any system of the q-classical orthogonal polynomials, and let be the corresponding weight function, satisfying the q-difference equation D_q(σ)=τ, where σ and τ are polynomials of degree at most 2 and exactly 1, respectively. Further, let {p_k⁽¹⁾(x;q)} be associated polynomials of the polynomials {p_k(x; q)}. Explicit forms of the coefficients b_n,k and c_n,k in the expansions

are given in terms of basic hypergeometric functions. Here _k(x) equals x^k if σ⁺(0)=0, or (x;q)_k if σ⁺(1)=0, where σ⁺(x)σ(x)+(q−1)xτ(x). The most important representatives of those two classes are the families of little q-Jacobi and big q-Jacobi polynomials, respectively.Writing the second-order nonhomogeneous q-difference equation satisfied by p_n−1⁽¹⁾(x;q) in a special form, recurrence relations (in k) for b_n,k and c_n,k are obtained in terms of σ and τ.