Weighted L p-Approximation of Derivatives by the Method of Gammaoperators

We consider Gammaoperators G _n on suitable Sobolev type subspaces of L _p(0, ∞) and characterize the global rate of approximation of derivatives f ^(r) through corresponding derivatives (G _n f)^(r) in an appropriate weighted L _p — metric by the rate of Ditzian and Totik’s second order weighted modulus of smoothness.     

Decomposition of the completer-graph into completer-partiter-graphs

Forn ≥ r ≥ 1, letf _r (n) denote the minimum numberq, such that it is possible to partition all edges of the completer-graph onn vertices intoq completer-partiter-graphs. Graham and Pollak showed thatf ₂(n) =n ? 1. Here we observe thatf ₃(n) =n ? 2 and show that for every fixedr ≥ 2, there are positive constantsc ₁(r) andc ₂(r) such thatc ₁(r) ≤f _r (n)?n ^?[r/2] ≤n ₂(r) for alln ≥ r. This solves a problem of Aharoni and Linial. The proof uses some simple ideas of linear algebra.     

Centralizers of generalized derivations on multilinear polynomials in prime rings

Let R be a prime ring of characteristic different from 2, with Utumi quotient ring U and extended centroid C, δ a nonzero derivation of R, G a nonzero generalized derivation of R, and f(x ₁, …, x _n ) a noncentral multilinear polynomial over C. If δ(G(f(r ₁, …, r _n ))f(r ₁, …, r _n )) = 0 for all r ₁, …, r _n ∈ R, then f(x ₁, …, x _n )² is central-valued on R. Moreover there exists a ∈ U such that G(x) = ax for all x ∈ R and δ is an inner derivation of R such that δ(a) = 0.     

Bipartite rainbow numbers of matchings

Given two graphs G and H, let f(G,H) denote the maximum number c for which there is a way to color the edges of G with c colors such that every subgraph H of G has at least two edges of the same color. Equivalently, any edge-coloring of G with at least rb(G,H)=f(G,H)+1 colors contains a rainbow copy of H, where a rainbow subgraph of an edge-colored graph is such that no two edges of it have the same color. The number rb(G,H) is called the rainbow number ofHwith respect toG, and simply called the bipartite rainbow number ofH if G is the complete bipartite graph K_m,n. Erd?s, Simonovits and Sós showed that rb(K_n,K₃)=n. In 2004, Schiermeyer determined the rainbow numbers rb(K_n,K_k) for all n≥k≥4, and the rainbow numbers rb(K_n,kK₂) for all k≥2 and n≥3k+3. In this paper we will determine the rainbow numbers rb(K_m,n,kK₂) for all k≥1.     

Edge-Colorings with No Large Polychromatic Stars

 Given a graph G and a positive integer r, let f _r (G) denote the largest number of colors that can be used in a coloring of E(G) such that each vertex is incident to at most r colors. For all positive integers n and r, we determine f _r (K _n,n ) exactly and f _r (K _n ) within 1. In doing so, we disprove a conjecture by Manoussakis, Spyratos, Tuza and Voigt in [4]. Received: May 17, 1999 Final version received: January 12, 2000     

Disjoint Kr-minors in large graphs with given average degree

It is proved that there are functions f(r) and N(r,s) such that for every positive integer r, s, each graph G with average degree d(G)=2|E(G)|/|V(G)|≥f(r), and with at least N(r,s) vertices has a minor isomorphic to K_r,s or to the union of s disjoint copies of K_r.     

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.     

Optimal labelling of a product of two paths

If G is a graph with p vertices and at least one edge, we set φ (G) = m n max |f(u) ? f(v)|, where the maximum is taken over all edges uv and the minimum over all one-to-one mappings f : V(G) → {1, 2, …, p}: V(G) denotes the set of vertices of G.P_n will denote a path of length n whose vertices are integers 1, 2, …, n with i adjacent to j if and only if |i ? j| = 1. P_m × P_n will denote a graph whose vertices are elements of {1, 2, …, m} × {1, 2, …, n} and in which (i, j), (r, s) are adjacent whenever either i = r and |j ? s| = 1 or j = s and |i ? r| = 1.Theorem.If max(m, n) ? 2, thenφ(P_m × P_n) = min(m, n).     

Near automorphisms of cycles

Let f be a permutation of V(G). Define δ_f(x,y)=|d_G(x,y)-d_G(f(x),f(y))| and δ_f(G)=∑δ_f(x,y) over all the unordered pairs {x,y} of distinct vertices of G. Let π(G) denote the smallest positive value of δ_f(G) among all the permutations f of V(G). The permutation f with δ_f(G)=π(G) is called a near automorphism of G. In this paper, we study the near automorphisms of cycles C_n and we prove that π(C_n)=4⌊n/2⌋-4, moreover, we obtain the set of near automorphisms of C_n.     

NP-completeness for minimizing maximum edge length in grid embeddings

Given an embedding f: G →$\text{Z}$² of a graph G in the two-dimensional lattice, let |f| be the maximum L₁ distance between points f(x) and f(y) where xy is an edge of G. Let B₂(G) be the minimum |f| over all embeddings f. It is shown that the determination of B₂(G) for arbitrary G is NP-complete. Essentially the same proof can be used in showing the NP-completeness of minimizing |f| over all embeddings f: G → $\text{Z}$ⁿ of G into the n-dimensional integer lattice for any fixed n ≥ 2.     

The profile of the Cartesian product of graphs

Given a graph G, a proper labelingf of G is a one-to-one function from V(G) onto {1,2,…,|V(G)|}. For a proper labeling f of G, the profile widthw_f(v) of a vertex v is the minimum value of f(v)−f(x), where x belongs to the closed neighborhood of v. The profile of a proper labelingfofG, denoted by P_f(G), is the sum of all the w_f(v), where v∈V(G). The profile ofG is the minimum value of P_f(G), where f runs over all proper labeling of G. In this paper, we show that if the vertices of a graph G can be ordered to satisfy a special neighborhood property, then so can the graph G×Q_n. This can be used to determine the profile of Q_n and K_m×Q_n.     

Isomorphisms,automorphisms, and generalized involution models of projective reflection groups

We investigate the generalized involution models of the projective reflection groups G(r, p, q, n). This family of groups parametrizes all quotients of the complex reflection groups G(r, p, n) by scalar subgroups. Our classification is ultimately incomplete, but we provide several necessary and sufficient conditions for generalized involution models to exist in various cases. In the process we solve several intermediate problems concerning the structure of projective reflection groups. We derive a simple criterion for determining whether two groups G(r, p, q, n) and G(r, p′, q′, n) are isomorphic. We also describe explicitly the form of all automorphisms of G(r, p, q, n), outside a finite list of exceptional cases. Building on prior work, this allows us to prove that G(r, p, 1, n) has a generalized involution model if and only if G(r, p, 1, n) ≌ G(r, 1, p, n). We also classify which groups G(r, p, q, n) have generalized involution models when n = 2, or q is odd, or n is odd.     

On the OBDD size for graphs of bounded tree- and clique-width

We study the size of OBDDs (ordered binary decision diagrams) for representing the adjacency function f_G of a graph G on n vertices. Our results are as follows:

-

for graphs of bounded tree-width there is an OBDD of size O(logn) for f_G that uses encodings of size O(logn) for the vertices;

-

for graphs of bounded clique-width there is an OBDD of size O(n) for f_G that uses encodings of size O(n) for the vertices;

-

for graphs of bounded clique-width such that there is a clique-width expression for G whose associated binary tree is of depth O(logn) there is an OBDD of size O(n) for f_G that uses encodings of size O(logn) for the vertices;

-

for cographs, i.e. graphs of clique-width at most 2, there is an OBDD of size O(n) for f_G that uses encodings of size O(logn) for the vertices. This last result complements a recent result by Nunkesser and Woelfel [R. Nunkesser, P. Woelfel, Representation of graphs by OBDDs, in: X. Deng, D. Du (Eds.), Proceedings of ISAAC 2005, in: Lecture Notes in Computer Science, vol. 3827, Springer, 2005, pp. 1132-1142] as it reduces the size of the OBDD by an O(logn) factor using encodings whose size is increased by an O(1) factor.

     

Piecewise Endomorphisms of Pid-Modules

Let G be a finitely generated module over a PID, D. We investigate the structure of the centralizer near-ring M_D(G) = {f: G → G ¦ f(ar) = (fa)r,a ∈ G, r ∈ D}. If C = {G_α} is a cover of G by maximal cyclic submodules then we show that every f ∈ M_D(G) is piecewise an endomorphism of G.     

Generators and commutators in finite groups; abstract quotients of compact groups

The first part of the paper establishes results about products of commutators in a d-generator finite group G, for example: if H?G=??g ₁,??,g _r ?? then every element of the subgroup [H,G] is a product of f(r) factors of the form $[h_{1},g_{1}][h_{1}^{\prime},g_{1}^{-1}]\ldots\lbrack h_{r},g_{r}][h_{r}^{\prime },g_{r}^{-1}]$ with $h_{1},h_{1}^{\prime},\ldots,\allowbreak h_{r},h_{r}^{\prime }\in H$ . Under certain conditions on H, a similar conclusion holds with the significantly weaker hypothesis that G=H??g ₁,??,g _r ??, where f(r) is replaced by f ₁(d,r). The results are applied in the second part of the paper to the study of normal subgroups in finitely generated profinite groups, and in more general compact groups. Results include the characterization of (topologically) finitely generated compact groups which have a countably infinite image, and of those which have a virtually dense normal subgroup of infinite index. As a corollary it is deduced that a compact group cannot have a finitely generated infinite abstract quotient.     

A class of antimagic join graphs

A labeling f of a graph G is a bijection from its edge set E(G) to the set {1, 2, . . . , |E(G)|}, which is antimagic if for any distinct vertices x and y, the sum of the labels on edges incident to x is different from the sum of the labels on edges incident to y. A graph G is antimagic if G has an f which is antimagic. Hartsfield and Ringel conjectured in 1990 that every connected graph other than K 2 is antimagic. In this paper, we show that if G 1 is an n-vertex graph with minimum degree at least r, and G 2 is an m-vertex graph with maximum degree at most 2r-1 (m ≥ n), then G1 ∨ G2 is antimagic.     

Non-generic unramified representations in metaplectic covering groups

Let G^(r) denote the metaplectic covering group of the linear algebraic group G. In this paper we study conditions on unramified representations of the group G^(r) not to have a nonzero Whittaker function. We state a general Conjecture about the possible unramified characters χ such that the unramified subrepresentation of \(Ind_{{B^{\left( r \right)}}}^{{G^{\left( r \right)}}}{X^{\delta _B^{1/2}}}\) will have no nonzero Whittaker function. We prove this Conjecture for the groups GL _n ^{( r)} with r ≥ n ? 1, and for the exceptional groups G ₂ ^{( r)} when r ≠ 2.     

n-Widths of Sobolev spaces inL p

LetW _p ^(r) ={f:f∈C ^r?1[0, 1],f ^(r?1) abs.cont., ∥f ^(r)∥ _p <∞}, and setB _p ^(r) ={f:f∈W _p ^(r) ,∥f ^(r)∥ _p ≤1}. We find the exact Kolmogorov, Gel'fand, linear, and Bernsteinn-widths ofB _p ^(r) inL ^p for allp∈(1, ∞). For the Kolmogorovn-width we show that forn≥r there exists an optimal subspace of splines of degreer?1 withn?r fixed simple knots depending onp.     

Bounds on the 2-Rainbow Domination Number of Graphs

A 2-rainbow domination function of a graph G is a function f that assigns to each vertex a set of colors chosen from the set {1, 2}, such that for any ${v\in V(G), f(v)=\emptyset}$ implies ${\bigcup_{u\in N(v)}f(u)=\{1,2\}.}$ The 2-rainbow domination number γ _r2(G) of a graph G is the minimum ${w(f)=\Sigma_{v\in V}|f(v)|}$ over all such functions f. Let G be a connected graph of order |V(G)| = n ≥ 3. We prove that γ _r2(G) ≤ 3n/4 and we characterize the graphs achieving equality. We also prove a lower bound for 2-rainbow domination number of a tree using its domination number. Some other lower and upper bounds of γ _r2(G) in terms of diameter are also given.