On <Emphasis Type="Italic">k</Emphasis>-pairable graphs from trees

The concept of the k-pairable graphs was introduced by Zhibo Chen (On k-pairable graphs, Discrete Mathematics 287 (2004), 11–15) as an extension of hypercubes and graphs with an antipodal isomorphism. In the same paper, Chen also introduced a new graph parameter p(G), called the pair length of a graph G, as the maximum k such that G is k-pairable and p(G) = 0 if G is not k-pairable for any positive integer k. In this paper, we answer the two open questions raised by Chen in the case that the graphs involved are restricted to be trees. That is, we characterize the trees G with p(G) = 1 and prove that p(G □ H) = p(G) + p(H) when both G and H are trees.     

（g,f）-FACTORS WITH SPECIAL PROPERTIES IN BIPARTITE （mg,mf）-GRAPHS

Let G be a bipartite graph and g and f be two positive integer-valued functions defined on vertex set V(G) of G such that g(x)≤f(x). In this paper,some sufficient conditions related to the connectivity and edge-connectivity for a bipartite (mg,mf)-graph to have a (g,f)-factor with special properties are obtained and some previous results are generalized.Furthermore,the new results are proved to be the best possible.     

The <Emphasis Type="Italic">k</Emphasis>-point exponent set of primitive digraphs with girth 2

Let D = （V, E） be a primitive digraph. The vertex exponent of D at a vertex v∈ V, denoted by expD（v）, is the least integer p such that there is a v →u walk of length p for each u ∈ V. Following Brualdi and Liu, we order the vertices of D so that exPD（V1） ≤ exPD（V2） …≤ exPD（Vn）. Then exPD（Vk） is called the k- point exponent of D and is denoted by exPD （k）, 1≤ k ≤ n. In this paper we define e（n, k） ：= max{expD （k） ｜ D ∈ PD（n, 2）} and E（n, k） ：= {exPD（k）｜ D ∈ PD（n, 2）}, where PD（n, 2） is the set of all primitive digraphs of order n with girth 2. We completely determine e（n, k） and E（n, k） for all n, k with n ≥ 3 and 1 ≤ k ≤ n.     

<Emphasis Type="Italic">f</Emphasis>-Vectors of barycentric subdivisions

For a simplicial complex or more generally Boolean cell complex Δ we study the behavior of the f- and h-vector under barycentric subdivision. We show that if Δ has a non-negative h-vector then the h-polynomial of its barycentric subdivision has only simple and real zeros. As a consequence this implies a strong version of the Charney–Davis conjecture for spheres that are the subdivision of a Boolean cell complex or the subdivision of the boundary complex of a simple polytope. For a general (d − 1)-dimensional simplicial complex Δ the h-polynomial of its n-th iterated subdivision shows convergent behavior. More precisely, we show that among the zeros of this h-polynomial there is one converging to infinity and the other d − 1 converge to a set of d − 1 real numbers which only depends on d. F. Brenti and V. Welker are partially supported by EU Research Training Network “Algebraic Combinatorics in Europe”, grant HPRN-CT-2001-00272 and the program on “Algebraic Combinatorics” at the Mittag-Leffler Institut in Spring 2005.     

On hamiltonicity of <Emphasis Type="Italic">P</Emphasis><Subscript>3</Subscript>-dominated graphs

We introduce a new class of graphs which we call P ₃-dominated graphs. This class properly contains all quasi-claw-free graphs, and hence all claw-free graphs. Let G be a 2-connected P ₃-dominated graph. We prove that G is hamiltonian if α(G ²) ≤ κ(G), with two exceptions: K _2,3 and K _1,1,3. We also prove that G is hamiltonian, if G is 3-connected and |V(G)| ≤ 5δ(G) − 5. These results extend known results on (quasi-)claw-free graphs. This paper was completed when both authors visited the Center for Combinatorics, Nankai University, Tianjin. They gratefully acknowledge the hospitality and support of the Center for Combinatorics and Nankai University. The work of E.Vumar is sponsored by SRF for ROCS, REM.     

The Roman <Emphasis Type="Italic">k</Emphasis>-domatic number of a graph

Let k be a positive integer. A Roman k-dominating function on a graph G is a labeling f: V (G) → {0, 1, 2} such that every vertex with label 0 has at least k neighbors with label 2. A set {f ₁, f ₂, …, f _d } of distinct Roman k-dominating functions on G with the property that Σ _i=1 ^d f _i (v) ≤ 2 for each v ∈ V (G), is called a Roman k-dominating family (of functions) on G. The maximum number of functions in a Roman k-dominating family on G is the Roman k-domatic number of G, denoted by d _kR (G). Note that the Roman 1-domatic number d _1R (G) is the usual Roman domatic number d _R (G). In this paper we initiate the study of the Roman k-domatic number in graphs and we present sharp bounds for d _kR (G). In addition, we determine the Roman k-domatic number of some graphs. Some of our results extend those given by Sheikholeslami and Volkmann in 2010 for the Roman domatic number.     

Computational study of large-scale <Emphasis Type="Italic">p</Emphasis>-Median problems

Given a directed graph G(V,A), the p-Median problem consists of determining p nodes (the median nodes) minimizing the total distance from the other nodes of the graph. We present a Branch-and-Cut-and-Price algorithm yielding provably good solutions for instances with |V|≤3795. Key ingredients of the algorithm are a delayed column-and-row generation technique, exploiting the special structure of the formulation, to solve the LP-relaxation, and cutting planes to strengthen the formulation and limit the size of the enumeration tree.     

<Emphasis Type="Italic">G</Emphasis>-compactness and groups

Lascar described E _KP as a composition of E _L and the topological closure of E _L (Casanovas et al. in J Math Log 1(2):305–319). We generalize this result to some other pairs of equivalence relations. Motivated by an attempt to construct a new example of a non-G-compact theory, we consider the following example. Assume G is a group definable in a structure M. We define a structure M′ consisting of M and X as two sorts, where X is an affine copy of G and in M′ we have the structure of M and the action of G on X. We prove that the Lascar group of M′ is a semi-direct product of the Lascar group of M and G/G _L . We discuss the relationship between G-compactness of M and M′. This example may yield new examples of non-G-compact theories. The first author is supported by the Polish Goverment grant N N201 384134. The second author is supported by the Polish Goverment grant N201 032 32/2231.     

On the b-Coloring of Cographs and <Emphasis Type="Italic">P</Emphasis><Subscript>4</Subscript>-Sparse Graphs

A b-coloring of a graph is a coloring such that every color class admits a vertex adjacent to at least one vertex receiving each of the colors not assigned to it. The b-chromatic number of a graph G, denoted by χ _b (G), is the maximum number t such that G admits a b-coloring with t colors. A graph G is b-continuous if it admits a b-coloring with t colors, for every . We define a graph G to be b-monotonic if χ _b (H ₁) ≥ χ _b (H ₂) for every induced subgraph H ₁ of G, and every induced subgraph H ₂ of H ₁. In this work, we prove that P ₄-sparse graphs (and, in particular, cographs) are b-continuous and b-monotonic. Besides, we describe a dynamic programming algorithm to compute the b-chromatic number in polynomial time within these graph classes. Flavia Bonomo: Partially supported by ANPCyT PICT-2007-00533 and PICT-2007-00518, and UBACyT Grants X069 and X606 (Argentina). Guillermo Durán: Partially supported by FONDECyT Grant 1080286 and Millennium Science Institute “Complex Engineering Systems” (Chile), and ANPCyT PICT-2007-00518 and UBACyT Grant X069 (Argentina). Javier Marenco: Partially supported by ANPCyT PICT-2007-00518 and UBACyT Grant X069 (Argentina).     

On the ideal (<Emphasis Type="Italic">v</Emphasis><Superscript>0</Superscript>)

The σ-ideal (v ⁰) is associated with the Silver forcing, see [5]. Also, it constitutes the family of all completely doughnut null sets, see [9]. We introduce segment topologies to state some resemblances of (v ⁰) to the family of Ramsey null sets. To describe add(v ⁰) we adopt a proof of Base Matrix Lemma. Consistent results are stated, too. Halbeisen’s conjecture cov(v ⁰) = add(v ⁰) is confirmed under the hypothesis t = min{cf(c), r}. The hypothesis cov(v ⁰) = ω ₁ implies that (v ⁰) has the ideal type (c, ω ₁, c).      

On Homomorphisms between <Emphasis Type="Italic">C</Emphasis>*-Algebras and Linear Derivations on <Emphasis Type="Italic">C</Emphasis>*-Algebras

It is shown that every almost linear Pexider mappings f, g, h from a unital C*-algebra into a unital C*-algebra ℬ are homomorphisms when f(2 ⁿ _uy) = f(2 ⁿ u)f(y), g(2 ⁿ uy) = g(2 ⁿ u)g(y) and h(2 ⁿ uy) = h(2 ⁿ u)h(y) hold for all unitaries u ∈ , all y ∈ , and all n ∈ ℤ, and that every almost linear continuous Pexider mappings f, g, h from a unital C*-algebra of real rank zero into a unital C*-algebra ℬ are homomorphisms when f(2 ⁿ uy) = f(2 ⁿ u)f(y), g(2 ⁿ uy) = g(2 ⁿ u)g(y) and h(2 ⁿ uy) = h(2 ⁿ u)h(y) hold for all u ∈ {v ∈ : v = v* and v is invertible}, all y ∈ and all n ∈ ℤ. Furthermore, we prove the Cauchy-Rassias stability of *-homomorphisms between unital C*-algebras, and ℂ-linear *-derivations on unital C*-algebras. This work was supported by Korea Research Foundation Grant KRF-2003-042-C00008. The second author was supported by the Brain Korea 21 Project in 2005.     

<Emphasis Type="Italic">∂</Emphasis>-operations and <Emphasis Type="Italic">H</Emphasis><Subscript><Emphasis Type="Italic">V</Emphasis></Subscript>-fields

The hyperoperations, called theta-operations （δ）, are motivated from the usual property, which the derivative has on the derivation of a product of functions. Using any map on a set, one can define δ-operations. In this paper, we continue our study on the δ-operations on groupoids, rings, fields and vector spaces or on the corresponding hyperstructures. Using δ-operations one obtains, mainly, Hwstructures, which form the largest class of the hyperstructures. For representation theory of hyperstructures, by hypermatrices, one needs special Hv-rings or Hy-fields, so these hyperstructures can be used. Moreover, we study the relation of these δ-structures with other classes of hyperstructures, especially with the Hv-structures.     

A note on <Emphasis Type="Italic">p</Emphasis>-groups of order ≤ <Emphasis Type="Italic">p</Emphasis><Superscript>4</Superscript>

In [1], we defined c(G), q(G) and p(G). In this paper we will show that if G is a p-group, where p is an odd prime and |G| ≤ p ⁴, then c(G) = q(G) = p(G). However, the question of whether or not there is a p-group G with strict inequality c(G) = q(G) < p(G) is still open.     

Zeros in Tables of Characters for the Groups <Emphasis Type="Italic">S</Emphasis><Subscript>n</Subscript> and <Emphasis Type="Italic">A</Emphasis><Subscript>n</Subscript>. II

Let P(n) be the set of all partitions of a natural number n. In the representation theory of symmetric groups, for every partition α ∈ P(n), the partition h(α) ∈ P(n) is defined so as to produce a certain set of zeros in the character table for S_n. Previously, the analog f(α) of h(α) was obtained pointing out an extra set of zeros in the table mentioned. Namely, h(α) is greatest (under the lexicographic ordering ≤) of the partitions β of n such that χ^α(g_β) ≠ 0, and f(α) is greatest of the partitions γ of n that are opposite in sign to h(α) and are such that χ^α(g_γ) ≠ 0, where χ^α is an irreducible character of S_n, indexed by α, and g_β is an element in the conjugacy class of S_n, indexed by β. For α ∈ P(n), under some natural restrictions, here, we construct new partitions h′(α) and f′(α) of n possessing the following properties. (A) Let α ∈ P(n) and n ⩾ 3. Then h′(α) is identical is sign to h(α), χ^α(g_h′(α)) ≠ 0, but χ^α(g_γ) = 0 for all γ ∈ P(n) such that the sign of γ coincides with one of h(α), and h′(α) < γ < h(α). (B) Let α ∈ P(n), α ≠ α′, and n ⩾ 4. Then f′(α) is identical in sign to f(α), χ^α(g_f′(α)) ≠ 0, but χ^α(g_γ) = 0 for all γ ∈ P(n) such that the sign of γ coincides with one of f(α), and f′(α) < γ < f(α). The results obtained are then applied to study pairs of semiproportional irreducible characters in A_n. Supported by RFBR grant No. 04-01-00463. __________ Translated from Algebra i Logika, Vol. 44, No. 6, pp. 643–663, November–December, 2005.     

On the prime graph of <Emphasis Type="Italic">PSL</Emphasis>(2, <Emphasis Type="Italic">p</Emphasis>) where <Emphasis Type="Italic">p</Emphasis> > 3 is a prime number

Let G be a finite group. We define the prime graph Γ(G) as follows. The vertices of Γ(G) are the primes dividing the order of G and two distinct vertices p, q are joined by an edge if there is an element in G of order pq. Recently M. Hagie [5] determined finite groups G satisfying Γ(G) = Γ(S), where S is a sporadic simple group. Let p > 3 be a prime number. In this paper we determine finite groups G such that Γ(G) = Γ(PSL(2, p)). As a consequence of our results we prove that if p > 11 is a prime number and p ≢ 1 (mod 12), then PSL(2, p) is uniquely determined by its prime graph and so these groups are characterizable by their prime graph. The third author was supported in part by a grant from IPM (No. 84200024).     

Acyclic total colorings of planar graphs without <Emphasis Type="Italic">l</Emphasis> cycles

A proper total coloring of a graph G such that there are at least 4 colors on those vertices and edges incident with a cycle of G, is called acyclic total coloring. The acyclic total chromatic number of G is the least number of colors in an acyclic total coloring of G. In this paper, it is proved that the acyclic total chromatic number of a planar graph G of maximum degree at least k and without l cycles is at most Δ(G) + 2 if (k, l) ∈ {(6, 3), (7, 4), (6, 5), (7, 6)}.     

Goal-minimally <Emphasis Type="Italic">k</Emphasis>-elongated graphs

Let k be an integer. A 2-edge connected graph G is said to be goal-minimally k-elongated (k-GME) if for every edge uv ∈ E(G) the inequality d _G−uv (x, y) > k holds if and only if {u, v} = {x, y}. In particular, if the integer k is equal to the diameter of graph G, we get the goal-minimally k-diametric (k-GMD) graphs. In this paper we construct some infinite families of GME graphs and explore k-GME and k-GMD properties of cages. This research was supported by the Slovak Scientific Grant Agency VEGA No. 1/0406/09.     

<Emphasis Type="Italic">Φ</Emphasis>-Variation of a bifractional Brownian motion

Let B _H,K = {B _H,K (t)} _t⩾0 be a bifractional Brownian motion with parameters H ∈ (0, 1) and K ∈ (0, 1]. For a function Φ: [0, ∞) → [0, ∞) and for a partition κ = {t _i }_n ⁱ⁼⁰ of an interval [0, T] with T > 0, let {ie418-01}. We prove that, for a suitable Φ depending on H and K, {ie418-02} almost surely. The research was partially supported by the Lithuanian State Science and Studies Foundation, grant No. T-16/08     

On the Nevanlinna characteristic of <Emphasis Type="Italic">f</Emphasis>(<Emphasis Type="Italic">z</Emphasis>+<Emphasis Type="Italic">η</Emphasis>) and difference equations in the complex plane

We investigate the growth of the Nevanlinna characteristic of f(z+η) for a fixed η∈C in this paper. In particular, we obtain a precise asymptotic relation between T(r,f(z+η)) and T(r,f), which is only true for finite order meromorphic functions. We have also obtained the proximity function and pointwise estimates of f(z+η)/f(z) which is a discrete version of the classical logarithmic derivative estimates of f(z). We apply these results to give new growth estimates of meromorphic solutions to higher order linear difference equations. This also allows us to solve an old problem of Whittaker (Interpolatory Function Theory, Cambridge University Press, Cambridge, 1935) concerning a first order difference equation. We show by giving a number of examples that all of our results are best possible in certain senses. Finally, we give a direct proof of a result in Ablowitz, Halburd and Herbst (Nonlinearity 13:889–905, 2000) concerning integrable difference equations. This research was supported in part by the Research Grants Council of the Hong Kong Special Administrative Region, China (HKUST6135/01P). The second author was also partially supported by the National Natural Science Foundation of China (Grant No. 10501044) and the HKUST PDF Matching Fund.     

A polynomial algorithm for finding (<Emphasis Type="Italic">g,f</Emphasis>)-colorings orthogonal to stars in bipartite graphs

Let G be a bipartite graph with vertex set V(G) and edge set E(G), and let g and f be two nonnegative integer-valued functions defined on V(G) such that g(x) ≤ f(x) for every vertex x of V(G). A (g, f)-coloring of G is a generalized edge-coloring in which each color appears at each vertex x at least g(x) and at most f(x) times. In this paper a polynomial algorithm to find a (g, f)-coloring of a bipartite graph with some constraints using the minimum number of colors is given. Furthermore, we show that the results in this paper are best possible.