Strongly regular locally <Emphasis Type="Italic">GQ</Emphasis>(4,<Emphasis Type="Italic">t</Emphasis>)-graphs

Amply regular with parameters (v, k, λ, μ) we call an undirected graph with v vertices in which the degrees of all vertices are equal to k, every edge belongs to λ triangles, and the intersection of the neighborhoods of every pair of vertices at distance 2 contains exactly μ vertices. An amply regular diameter 2 graph is called strongly regular. We prove the nonexistence of amply regular locally GQ(4,t)-graphs with (t,μ) = (4, 10) and (8, 30). This reduces the classification problem for strongly regular locally GQ(4,t)-graphs to studying locally GQ(4, 6)-graphs with parameters (726, 125, 28, 20).     

On strongly regular graphs with <Emphasis Type="Italic">b</Emphasis><Subscript>1</Subscript> &lt; 24

Let γ be a connected edge-regular graph with parameters (v, k, λ), and let b ₁ = k?λ?1. It is well known that, if b ₁ = 1, then Γ is either a polygon or a complete multipartite graph with parts of order 2. Graphs with b ₁ ≤ 4 were classified earlier. The investigation of graphs even in the case b ₁ = 5 involves great difficulties. However, for strongly regular graphs, the situation is much simpler. In this paper, we classify strongly regular graphs with b ₁ < 24.     

On almost good triples of vertices in edge regular graphs

Consider a connected edge regular graph Γ with parameters (v, k, λ) and put b ₁ = k?λ?1. A triple (u, w, z) of vertices is called (almost) good whenever d(u, w) = d(u, z) = 2 and µ(u, w)+µ(u, z) ≤ 2k ? 4b ₁ + 3 (and µ(u, w) + µ(u, z) = 2k ? 4b ₁ + 4). If k = 3b ₁ + γ with γ ≥ ?2, a triple (u, w, z) is almost good, and Δ = [u] ∩ [w] ∩ [z] then: either |Δ| ≤ 2; or Δ is a 3-clique and Γ is a Clebsch graph; or Δ is a 3-clique, k = 16, b ₁ = 6, and v = 31; or Δ is a 4-clique and Γ is a Schläfli graph.     

Distance-Regular Shilla Graphs with <Emphasis Type="Italic">b</Emphasis><Subscript>2</Subscript> = <Emphasis Type="Italic">c</Emphasis><Subscript>2</Subscript>

A Shilla graph is defined as a distance-regular graph of diameter 3 with second eigen-value θ₁ equal to a₃. For a Shilla graph, let us put a = a₃ and b = k/a. It is proved in this paper that a Shilla graph with b₂ = c₂ and noninteger eigenvalues has the following intersection array:

$$\left\{ {\frac{{{b^2}\left( {b - 1} \right)}}{2},\frac{{\left( {b - 1} \right)\left( {{b^2} - b + 2} \right)}}{2},\frac{{b\left( {b - 1} \right)}}{4};1,\frac{{b\left( {b - 1} \right)}}{4},\frac{{b{{\left( {b - 1} \right)}^2}}}{2}} \right\}$$

If Γ is a Q-polynomial Shilla graph with b₂ = c₂ and b = 2r, then the graph Γ has intersection array

$$\left\{ {2tr\left( {2r + 1} \right),\left( {2r + 1} \right)\left( {2rt + t + 1} \right),r\left( {r + t} \right);1,r\left( {r + t} \right),t\left( {4{r^2} - 1} \right)} \right\}$$

and, for any vertex u in Γ, the subgraph Γ₃(u) is an antipodal distance-regular graph with intersection array

$$\left\{ {t\left( {2r + 1} \right),\left( {2r - 1} \right)\left( {t + 1} \right),1;1,t + 1,t\left( {2r + 1} \right)} \right\}$$

The Shilla graphs with b₂ = c₂ and b = 4 are also classified in the paper.

     

Planar Graded Lattices and the <Emphasis Type="Bold">c</Emphasis><Subscript>1</Subscript>-Median Property

Let L be a lattice of finite length, ξ = (x ₁,…, x _k )∈L ^k , and y ∈ L. The remoteness r(y, ξ) of y from ξ is d(y, x ₁)+?+d(y, x _k ), where d stands for the minimum path length distance in the covering graph of L. Assume, in addition, that L is a graded planar lattice. We prove that whenever r(y, ξ) ≤ r(z, ξ) for all z ∈ L, then y ≤ x ₁∨?∨x _k . In other words, L satisfies the so-called c ₁ -median property.     

On <Emphasis Type="Italic">K</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis>,<Emphasis Type="Italic">q</Emphasis></Subscript>-factorization of complete bipartite multigraphs

Let λK _m,n be a complete bipartite multigraph with two partite sets having m and n vertices, respectively. A K _p,q -factorization of λK _m,n is a set of edge-disjoint K _p,q -factors of λK _m,n which partition the set of edges of λK _m,n . When p = 1 and q is a prime number, Wang, in his paper [On K _1,q -factorization of complete bipartite graph, Discrete Math., 126: (1994), 359-364], investigated the K _1,q -factorization of K _m,n and gave a sufficient condition for such a factorization to exist. In papers [K _1,k -factorization of complete bipartite graphs, Discrete Math., 259: 301-306 (2002),; K _p,q -factorization of complete bipartite graphs, Sci. China Ser. A-Math., 47: (2004), 473-479], Du and Wang extended Wang’s result to the case that p and q are any positive integers. In this paper, we give a sufficient condition for λK _m,n to have a K _p,q -factorization. As a special case, it is shown that the necessary condition for the K _p,q -factorization of λK _m,n is always sufficient when p : q = k : (k + 1) for any positive integer k.     

<Emphasis Type="Italic">L</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis></Subscript>-boundedness of a boundary integral operator on a contour with a peak

Results on the solvability of boundary integral equations on a plane contour with a peak obtained in collaboration with V.G. Maz’ya are developed. Earlier, it was proved that, on a contour Γ with an outward peak, the operator of the boundary equation of the Dirichlet boundary value problem maps the space ? _{p, β + 1} (Γ) continuously onto \(\mathcal{N}_{p,\beta } (\Gamma )\). The norm of a function in ? _{p, β} (Γ) is defined as

Open image in new window

, provided that the peak is at the origin. In this case, the norms on the spaces \(\mathcal{N}_{p,\beta }^ \mp (\Gamma )\) are defined by

Open image in new window

, where q _± are the intersection points of Γ with the circle {z: |z| = |q|} and δ > 0 is a fixed small number. On a contour with an inward peak, the operator of the boundary equation of the Dirichlet problem continuously maps ? _{p, β + 1} (Γ) onto ? _{p, β}(Γ), where ? _{p, β}(Γ) is the direct sum of \(\mathcal{N}_{p,\beta }^ + (\Gamma )\) (Γ) and the space

Open image in new window

(Γ) of functions on Γ of the form p(z) = Σ _{k = 0} ^m t ^(k)Rez ^k with the parameter m = [μ ? β ? p ^?1]. The operator I ? 2W of the boundary integral equation of plane elasticity theory, where W is the elastic double-layer potential, is considered. The main result is that the operator I ? 2W continuously maps the space ? _{p, β + 1} × ? _{p, β + 1}(Γ) to the space \(\mathcal{N}_{p,\beta }^ - \times \mathcal{N}_{p,\beta }^ - (\Gamma )\).

On a contour with an inward peak, the obtained representation of the operator I ? 2W and theorems on the boundedness of auxiliary integral operators imply that the images of vector-valued functions from ? _{p, β + 1} × ? _{p, β + 1}(Γ) have components representable as sums of functions from the spaces \(\mathcal{N}_{p,\beta }^ - (\Gamma )\)(Γ) and ? _{p, β}(Γ).     

Neighbor sum distinguishing total chromatic number of <Emphasis Type="Italic">K</Emphasis><Subscript>4</Subscript>-minor free graph

A k-total coloring of a graph G is a mapping ?: V (G) ? E(G) → {1; 2,..., k} such that no two adjacent or incident elements in V (G) ? E(G) receive the same color. Let f(v) denote the sum of the color on the vertex v and the colors on all edges incident with v: We say that ? is a k-neighbor sum distinguishing total coloring of G if f(u) 6 ≠ f(v) for each edge uv ∈ E(G): Denote χ _Σ ^″ (G) the smallest value k in such a coloring of G: Pil?niak and Wo?niak conjectured that for any simple graph with maximum degree Δ(G), χ _Σ ^″ ≤ Δ(G)+3. In this paper, by using the famous Combinatorial Nullstellensatz, we prove that for K ₄-minor free graph G with Δ(G) > 5; χ _Σ ^″ = Δ(G) + 1 if G contains no two adjacent Δ-vertices, otherwise, χ _Σ ^″ (G) = Δ(G) + 2.     

On <Emphasis Type="Italic">r</Emphasis>-recognition by prime graph of <Emphasis Type="Italic">B</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis></Subscript>(3) where <Emphasis Type="Italic">p</Emphasis> is an odd prime

Let G be a finite group. The prime graph Γ(G) of G is defined as follows. The vertices of Γ(G) are the primes dividing the order of G and two distinct vertices p and p′ are joined by an edge if there is an element in G of order pp′. We denote by k(Γ(G)) the number of isomorphism classes of finite groups H satisfying Γ(G) = Γ(H). Given a natural number r, a finite group G is called r-recognizable by prime graph if k(Γ(G)) =  r. In Shen et al. (Sib. Math. J. 51(2):244–254, 2010), it is proved that if p is an odd prime, then B _p (3) is recognizable by element orders. In this paper as the main result, we show that if G is a finite group such that Γ(G) = Γ(B _p (3)), where p > 3 is an odd prime, then \({G\cong B_p(3)}\) or C _p (3). Also if Γ(G) = Γ(B ₃(3)), then \({G\cong B_3(3), C_3(3), D_4(3)}\), or \({G/O_2(G)\cong {\rm Aut}(^2B_2(8))}\). As a corollary, the main result of the above paper is obtained.     

On balanced colorings of the <Emphasis Type="Italic">n</Emphasis>-cube

A 2-coloring of the n-cube in the n-dimensional Euclidean space can be considered as an assignment of weights of 1 or 0 to the vertices. Such a colored n-cube is said to be balanced if its center of mass coincides with its geometric center. Let B _n,2k be the number of balanced 2-colorings of the n-cube with 2k vertices having weight 1. Palmer, Read, and Robinson conjectured that for n≥1, the sequence \(\{B_{n,2k}\}_{k=0,1,\ldots,2^{n-1}}\) is symmetric and unimodal. We give a proof of this conjecture. We also propose a conjecture on the log-concavity of B _n,2k for fixed k, and by probabilistic method we show that it holds when n is sufficiently large.     

On the automorphism group of the Aschbacher graph

A Moore graph is a regular graph of degree k and diameter d with v vertices such that v ≤ 1 + k + k(k ? 1) + ... + k(k ? 1)^d?1. It is known that a Moore graph of degree k ≥ 3 has diameter 2; i.e., it is strongly regular with parameters λ = 0, µ = 1, and v = k ² + 1, where the degree k is equal to 3, 7, or 57. It is unknown whether there exists a Moore graph of degree k = 57. Aschbacher showed that a Moore graph with k = 57 is not a graph of rank 3. In this connection, we call a Moore graph with k = 57 the Aschbacher graph and investigate its automorphism group G without additional assumptions (earlier, it was assumed that G contains an involution).     

Automorphisms of Coxeter groups of type <Emphasis Type="Italic">K</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript>

A Coxeter system (W, S) is said to be of type K _n if the associated Coxeter graph Γ_S is complete on n vertices and has only odd edge labels. If W satisfies either of: (1) n = 3; (2) W is rigid; then the automorphism group of W is generated by the inner automorphisms of W and any automorphisms induced by Γ_S. Indeed, Aut(W) is the semidirect product of Inn(W) and the group of diagram automorphisms, and furthermore W is strongly rigid. We also show that if W is a Coxeter group of type K _n then W has exactly one conjugacy class of involutions and hence Aut(W) = Spec(W).     

Degree sum of a pair of independent edges and <Emphasis Type="Italic">Z</Emphasis><Subscript>3</Subscript>-connectivity

Let G be a 2-edge-connected simple graph on n vertices. For an edge e = uv ∈ E(G), define d(e) = d(u) + d(v). Let F denote the set of all simple 2-edge-connected graphs on n ≥ 4 vertices such that G ∈ F if and only if d(e) + d(e’) ≥ 2n for every pair of independent edges e, e’ of G. We prove in this paper that for each G ∈ F, G is not Z ₃-connected if and only if G is one of K _2,n?2, K _3,n?3, K _2,n?2 ⁺ , K _3,n?3 ⁺ or one of the 16 specified graphs, which generalizes the results of X. Zhang et al. [Discrete Math., 2010, 310: 3390–3397] and G. Fan and X. Zhou [Discrete Math., 2008, 308: 6233–6240].     

The Number of <Emphasis Type="Italic">k</Emphasis>-Sumsets in an Abelian Group

Let G be an abelian group of order n. The sum of subsets A₁,...,A_k of G is defined as the collection of all sums of k elements from A₁,...,A_k; i.e., A₁ + A₂ + · · · + A_k = {a₁ + · · · + a_k | a₁ ∈ A₁,..., a_k ∈ A_k}. A subset representable as the sum of k subsets of G is a k-sumset. We consider the problem of the number of k-sumsets in an abelian group G. It is obvious that each subset A in G is a k-sumset since A is representable as A = A₁ + · · · + A_k, where A₁ = A and A₂ = · · · = A_k = {0}. Thus, the number of k-sumsets is equal to the number of all subsets of G. But, if we introduce a constraint on the size of the summands A₁,...,A_k then the number of k-sumsets becomes substantially smaller. A lower and upper asymptotic bounds of the number of k-sumsets in abelian groups are obtained provided that there exists a summand A_i such that |A_i| = n log^qn and |A₁ +· · ·+ A_i-1 + A_i+1 + · · ·+A_k| = n log^qn, where q = -1/8 and i ∈ {1,..., k}.     

Equivalence of two definitions of a generalized <Emphasis Type="Italic">L</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis></Subscript> solution to the initial-boundary value problem for the wave equation

In our previous papers, we introduced the notion of a generalized solution to the initial-boundary value problem for the wave equation with a boundary function µ(t) such that the integral ∫ ₀ ^T (T ? t)|µ(t)| ^p dt exists. Here we prove that this solution is a unique solution to the problem in L _p that satisfies the corresponding integral identity.     

On a new property of <Emphasis Type="Italic">n</Emphasis>-poised and <Emphasis Type="Italic">G</Emphasis><Emphasis Type="Italic">C</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript> sets

In this paper we consider n-poised planar node sets, as well as more special ones, called G C _n sets. For the latter sets each n-fundamental polynomial is a product of n linear factors as it always holds in the univariate case. A line ? is called k-node line for a node set \(\mathcal X\) if it passes through exactly k nodes. An (n + 1)-node line is called maximal line. In 1982 M. Gasca and J. I. Maeztu conjectured that every G C _n set possesses necessarily a maximal line. Till now the conjecture is confirmed to be true for n ≤ 5. It is well-known that any maximal line M of \(\mathcal X\) is used by each node in \(\mathcal X\setminus M, \)meaning that it is a factor of the fundamental polynomial. In this paper we prove, in particular, that if the Gasca-Maeztu conjecture is true then any n-node line of G C _n set \(\mathcal {X}\) is used either by exactly \(\binom {n}{2}\) nodes or by exactly \(\binom {n-1}{2}\) nodes. We prove also similar statements concerning n-node or (n ? 1)-node lines in more general n-poised sets. This is a new phenomenon in n-poised and G C _n sets. At the end we present a conjecture concerning any k-node line.     

On <Emphasis Type="Italic">K</Emphasis><Subscript>1,3</Subscript>-free strictly Deza graphs

A graph on v vertices is called a Deza graph with parameters (v, k, b, a) if it is k-regular and the number of common neighbors of two distinct vertices takes on one of two values. We describe strictly Deza graphs that do not contain K _1,3 among their induced subgraphs and are unions of closed neighborhoods of two nonadjacent vertices. The latter condition means that there are two nonadjacent vertices such that any other vertex is adjacent to at least one of the them.     

On Linear Preservers of Two-Sided Gut-Majorization On <Emphasis Type="Bold">M</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis>,<Emphasis Type="Italic">m</Emphasis></Subscript>

For X, Y ∈ M_n,m it is said that X is gut-majorized by Y, and we write X ?_gutY, if there exists an n-by-n upper triangular g-row stochastic matrix R such that X = RY. Define the relation ~_gut as follows. X ~_gutY if X is gut-majorized by Y and Y is gut-majorized by X. The (strong) linear preservers of ?_gut on ?ⁿ and strong linear preservers of this relation on M_n,m have been characterized before. This paper characterizes all (strong) linear preservers and strong linear preservers of ~_gut on ?ⁿ and M_n,m.     

Amply regular graphs with Hoffman’s condition

It is known that, if the minimal eigenvalue of a graph is ?2, then the graph satisfies Hoffman’s condition: for any generated complete bipartite subgraph K _1,3 (a 3-claw) with parts {p} and {q ₁, q ₂, q ₃}, any vertex distinct from p and adjacent to the vertices q ₁ and q ₂ is adjacent to p but not adjacent to q ₃. We prove the converse statement for amply regular graphs containing a 3-claw and satisfying the condition µ > 1.     

The <Emphasis Type="Italic">p</Emphasis>-Adic order of the <Emphasis Type="Italic">k</Emphasis>-Fibonacci and <Emphasis Type="Italic">k</Emphasis>-Lucas numbers

Let (F _k,n ) _n and (L _k,n )n be the k-Fibonacci and k-Lucas sequence, respectively, which satisfies the same recursive relation a _n+1 = ka _n + a _n?1 with initial values F _k,0 = 0, F _k,1 = 1, L _k,0 = 2 and L _k,1 = k. In this paper, we characterize the p-adic orders ν _p (F _k,n ) and ν _p (L _k,n ) for all primes p and all positive integers k.