The starlike trees with maximum and minimum second order connectivity index

Let G be a simple graph and h≥0 be an integer. The higher order connectivity index R _h (G) of G is defined as $$R_h(G)=\sum_{v_{i_1}v_{i_2}\cdots v_{i_{h+1}}} \frac{1}{\sqrt {d_{i_1}d_{i_2}\cdots d_{i_{h+1}}}},$$ where d _i denotes the degree of the vertex v _i and $v_{i_{1}}v_{i_{2}}\cdots v_{i_{h+1}}$ runs over all paths of length h in G. A starlike tree is a tree with unique vertex of degree greater than two. Rada and Araujo proved that the starlike trees which have equal connectivity index of order h for all h≥0 are isomorphic. By T(n) we denote the set of the starlike trees on n vertices. In this paper, we characterize the extremal starlike trees with maximum and minimum second order connectivity index in T(n).     

A relation between the Laplacian and signless Laplacian eigenvalues of a graph

Let G be a graph of order n such that \(\sum_{i=0}^{n}(-1)^{i}a_{i}\lambda^{n-i}\) and \(\sum_{i=0}^{n}(-1)^{i}b_{i}\lambda^{n-i}\) are the characteristic polynomials of the signless Laplacian and the Laplacian matrices of G, respectively. We show that a _i ≥b _i for i=0,1,…,n. As a consequence, we prove that for any α, 0<α≤1, if q ₁,…,q _n and μ ₁,…,μ _n are the signless Laplacian and the Laplacian eigenvalues of G, respectively, then \(q_{1}^{\alpha}+\cdots+q_{n}^{\alpha}\geq\mu_{1}^{\alpha}+\cdots+\mu _{n}^{\alpha}\).     

On Bipartite Distance-Regular Graphs with Intersection Numbers c i = (q i ? 1)/(q ? 1)

Let q denote an integer at least two. Let ?? denote a bipartite distance-regular graph with diameter D ?? 3 and intersection numbers c _i = (q ⁱ ? 1)/(q ? 1), 1 ?? i ?? D. Let X denote the vertex set of ?? and let ${V = \mathbb{C}^X}$ denote the vector space over ${\mathbb{C}}$ consisting of column vectors whose coordinates are indexed by X and whose entries are in ${\mathbb{C}}$ . For ${z \in X}$ , let ${{\hat z}}$ denote the vector in V with a 1 in the z-coordinate and 0 in all other coordinates. Fix ${x, y \in X}$ such that ?(x, y) = 2, where ? denotes the path-length distance function. For 0 ?? i, j ?? D define ${w_{ij} = \sum {\hat z}}$ , where the sum is over all ${z \in X}$ such that ?(x, z) = i and ?(y, z) = j. We define W?=?span{w _ij | 0 ?? i, j ?? D}. In this paper we consider the space ${MW={\rm span} \{mw \mid m \in M, w \in W\}}$ , where M is the Bose?CMesner algebra of ??. We observe that MW is the minimal A-invariant subspace of V which contains W, where A is the adjacency matrix of ??. We give a basis for MW that is orthogonal with respect to the Hermitean dot product. We compute the square-norm of each basis vector. We compute the action of A on the basis. For the case in which ?? is the dual polar graph D _D (q) we show that the basis consists of the characteristic vectors of the orbits of the stabilizer of x and y in the automorphism group of ??.     

Adjacency matrices of polarity graphs and of other C 4-free graphs of large size

In this paper we give a method for obtaining the adjacency matrix of a simple polarity graph G _q from a projective plane PG(2, q), where q is a prime power. Denote by ex(n; C ₄) the maximum number of edges of a graph on n vertices and free of squares C ₄. We use the constructed graphs G _q to obtain lower bounds on the extremal function ex(n; C ₄), for some n < q ² + q + 1. In particular, we construct a C ₄-free graph on ${n=q^2 -\sqrt{q}}$ vertices and ${\frac{1}{2} q(q^2-1)-\frac{1}{2}\sqrt{q} (q-1) }$ edges, for a square prime power q.     

On Graphlike k-Dissimilarity Vectors

Let \({\mathcal{G} = (G, w)}\) be a positive-weighted simple finite connected graph, that is, let G be a simple finite connected graph endowed with a function w from the set of edges of G to the set of positive real numbers. For any subgraph \({G^\prime}\) of G, we define \({w(G^\prime)}\) to be the sum of the weights of the edges of \({G^\prime}\) . For any i ₁, . . . , i _k vertices of G, let \({D_{\{i_1,..., i_k\}} (\mathcal{G})}\) be the minimum of the weights of the subgraphs of G connecting i ₁, . . . , i _k . The \({D_{\{i_1,..., i_k\}}(\mathcal{G})}\) are called k-weights of \({\mathcal{G}}\) . Given a family of positive real numbers parametrized by the k-subsets of {1, . . . , n}, \({{\{D_I\}_{I} \in { \{1,...,n\} \choose k}}}\) , we can wonder when there exist a weighted graph \({\mathcal{G}}\) (or a weighted tree) and an n-subset {1, . . . , n} of the set of its vertices such that \({D_I (\mathcal{G}) = D_I}\) for any \({I} \in { \{1,...,n\} \choose k}\) . In this paper we study this problem in the case k =  n?1.     

Uniqueness properties of degenerate elliptic operators

Let ?? be an open subset of R ^d and ${ K=-\sum^d_{i,j=1}\partial_i\,c_{ij}\,\partial_j+\sum^d_{i=1}c_i\partial_i+c_0}$ a second-order partial differential operator with real-valued coefficients ${c_{ij}=c_{ji}\in W^{1,\infty}_{\rm loc}(\Omega),c_i,c_0\in L_{\infty,{\rm loc}}(\Omega)}$ satisfying the strict ellipticity condition ${C=(c_{ij}) >0 }$ . Further let ${H=-\sum^d_{i,j=1} \partial_i\,c_{ij}\,\partial_j}$ denote the principal part of K. Assuming an accretivity condition ${C\geq \kappa (c\otimes c^{\,T})}$ with ${\kappa >0 }$ , an invariance condition ${(1\!\!1_\Omega, K\varphi)=0}$ and a growth condition which allows ${\|C(x)\|\sim |x|^2\log |x|}$ as |x| ?? ?? we prove that K is L ₁-unique if and only if H is L ₁-unique or Markov unique.     

Rainbow Connection Number, Bridges and Radius

Let G be a connected graph. The notion of rainbow connection number rc(G) of a graph G was introduced by Chartrand et al. (Math Bohem 133:85–98, 2008). Basavaraju et al. (arXiv:1011.0620v1 [math.CO], 2010) proved that for every bridgeless graph G with radius r, ${rc(G)\leq r(r+2)}$ and the bound is tight. In this paper, we show that for a connected graph G with radius r and center vertex u, if we let D ^r  = {u}, then G has r?1 connected dominating sets ${ D^{r-1}, D^{r-2},\ldots, D^{1}}$ such that ${D^{r} \subset D^{r-1} \subset D^{r-2} \cdots\subset D^{1} \subset D^{0}=V(G)}$ and ${rc(G)\leq \sum_{i=1}^{r} \max \{2i+1,b_i\}}$ , where b _i is the number of bridges in E[D ⁱ , N(D ⁱ )] for ${1\leq i \leq r}$ . From the result, we can get that if ${b_i\leq 2i+1}$ for all ${1\leq i\leq r}$ , then ${rc(G)\leq \sum_{i=1}^{r}(2i+1)= r(r+2)}$ ; if b _i  > 2i + 1 for all ${1\leq i\leq r}$ , then ${rc(G)= \sum_{i=1}^{r}b_i}$ , the number of bridges of G. This generalizes the result of Basavaraju et al. In addition, an example is given to show that there exist infinitely graphs with bridges whose rc(G) is only dependent on the radius of G, and another example is given to show that there exist infinitely graphs with bridges whose rc(G) is only dependent on the number of bridges in G.     

The Domination Polynomial of a Graph at −1

Let G be a simple graph. The domination polynomial of a graph G of order n is the polynomial ${D(G,x)=\sum_{i=0}^{n} d(G,i) x^{i}}$ , where d(G, i) is the number of dominating sets of G of size i. In this article we investigate the domination polynomial at ?1. We give a construction showing that for each odd number n there is a connected graph G with D(G, ?1) = n.     

Two Linear Transformations each Tridiagonal with Respect to an Eigenbasis of the other; Comments on the Parameter Array

Let ${\mathbb K} $ denote a field. Let it d denote a nonnegative integer and consider a sequence p=( $\theta_i, \theta^*_i,i=0...d; \varphi_j, \phi_j,j=1...{\it d})$ consisting of scalars taken from ${\mathbb K} $ . We call p a parameter array whenever: (PA1) $\theta_i \not=\theta_j, \; \theta^*_i\not=\theta^*_j$ if $$i\not=j$, $(0 \leq i, j\leq d)$; (PA2) $ \varphi_i\not=0$, $\phi_i\not=0$ $(1 \leq i \leq d)$; (PA3) $\varphi_i = \phi_1 \sum_{h=0}^{i-1} ({\theta_h-\theta_{d-h}})/({\theta_0-\theta_d}) + (\theta^*_i-\theta^*_0)(\theta_{i-1}-\theta_d)$ $(1 \leq i \leq d)$; (PA4) $\phi_i = \varphi_1 \sum_{h=0}^{i-1} ({\theta_h-\theta_{d-h}})/({\theta_0-\theta_d}) + (\theta^*_i-\theta^*_0)(\theta_{d-i+1}-\theta_0)$ $(1 \leq i \leq d)$; (PA5) $(\theta_{i-2}-\theta_{i+1})(\theta_{i-1}-\theta_i)^{-1}$, $(\theta^*_{i-2}-\theta^*_{i+1})(\theta^*_{i-1}-\theta^*_i)^{-1}$$ are equal and independent of i for $2 \leq i \leq d-1$ . In Terwilliger, J. Terwilliger, Linear Algebra Appl., Vol. 330(2001) p. 155 we showed the parameter arrays are in bijection with the isomorphism classes of Leonard systems. Using this bijection we obtain the following two characterizations of parameter arrays. Assume p satisfies PA1 and PA2. Let A, B,A^*, B^* denote the matrices in ${Mat}_{{\it d}+1}$ ( ${\mathbb K} $ ) which have entries A _ii =θ _i , B _ii =θ _d-i , A ^* _ii =θ^* _i , B ^* _ii =θ^* _i (0 ≤ i ≤ d), A _i,i-1=1, B _i,i-1=1, A ^* _i-1,i =φ _i , B ^* _i-1,i =? _i (1 ≤ i ≤ d), and all other entries 0. We show the following are equivalent: (i) p satisfies PA3–PA5; (ii) there exists an invertible G ∈Mat _d+1( ${\mathbb K} $ ) such that G ^?1 AG=B and G ^?1 A ^* G=B ^*; (iii) for 0 ≤ i ≤ d the polynomial $$ \sum_{n=0}^i \frac{ (\lambda-\theta_0) (\lambda-\theta_1) \cdots (\lambda-\theta_{n-1}) (\theta^*_i-\theta^*_0) (\theta^*_i-\theta^*_1) \cdots (\theta^*_i-\theta^*_{n-1}) } {\varphi_1\varphi_2\cdots \varphi_n}$$ is a scalar multiple of the polynomial $$\sum_{n=0}^i \frac{ (\lambda-\theta_d) (\lambda-\theta_{d-1}) \cdots (\lambda-\theta_{d-n+1}) (\theta^*_i-\theta^*_0) (\theta^*_i-\theta^*_1) \cdots (\theta^*_i-\theta^*_{n-1}) } {\phi_1\phi_2\cdots \phi_n}.$$ We display all the parameter arrays in parametric form. For each array we compute the above polynomials. The resulting polynomials form a class consisting of the q-Racah, q-Hahn, dual q-Hahn, q-Krawtchouk, dual q-Krawtchouk, quantum q-Krawtchouk, affine q-Krawtchouk, Racah, Hahn, dual-Hahn, Krawtchouk, Bannai/Ito, and Orphan polynomials. The Bannai/Ito polynomials can be obtained from the q-Racah polynomials by letting q tend to ?1. The Orphan polynomials have maximal degree 3 and exist for ( ${\mathbb K} $ )=2 only. For each of the polynomials listed above we give the orthogonality, 3-term recurrence, and difference equation in terms of the parameter array.     

Resolvability in circulant graphs

A set W of the vertices of a connected graph G is called a resolving set for G if for every two distinct vertices u, v ∈ V (G) there is a vertex w ∈ W such that d(u, w) ≠ d(v, w). A resolving set of minimum cardinality is called a metric basis for G and the number of vertices in a metric basis is called the metric dimension of G, denoted by dim(G). For a vertex u of G and a subset S of V (G), the distance between u and S is the number min s∈S d(u, s). A k-partition Π = {S 1 , S 2 , . . . , S k } of V (G) is called a resolving partition if for every two distinct vertices u, v ∈ V (G) there is a set S i in Π such that d(u, Si )≠ d(v, Si ). The minimum k for which there is a resolving k-partition of V (G) is called the partition dimension of G, denoted by pd(G). The circulant graph is a graph with vertex set Zn , an additive group of integers modulo n, and two vertices labeled i and j adjacent if and only if i-j (mod n) ∈ C , where CZn has the property that C =-C and 0 ■ C. The circulant graph is denoted by Xn, Δ where Δ = |C|. In this paper, we study the metric dimension of a family of circulant graphs Xn, 3 with connection set C = {1, n/2 , n-1} and prove that dim(Xn, 3 ) is independent of choice of n by showing that dim(Xn, 3 ) ={3 for all n ≡ 0 (mod 4), 4 for all n ≡ 2 (mod 4). We also study the partition dimension of a family of circulant graphs Xn,4 with connection set C = {±1, ±2} and prove that pd(Xn, 4 ) is independent of choice of n and show that pd(X5,4 ) = 5 and pd(Xn,4 ) ={3 for all odd n ≥ 9, 4 for all even n ≥ 6 and n = 7.     

A Congruence Connecting Latin Rectangles and Partial Orthomorphisms

A partial orthomorphism of ${\mathbb{Z}_{n}}$ is an injective map ${\sigma : S \rightarrow \mathbb{Z}_{n}}$ such that ${S \subseteq \mathbb{Z}_{n}}$ and ??(i)?Ci ? ??(j)? j (mod n) for distinct ${i, j \in S}$ . We say ?? has deficit d if ${|S| = n - d}$ . Let ??(n, d) be the number of partial orthomorphisms of ${\mathbb{Z}_{n}}$ of deficit d. Let ??(n, d) be the number of partial orthomorphisms ?? of ${\mathbb{Z}_n}$ of deficit d such that ??(i) ? {0, i} for all ${i \in S}$ . Then ??(n, d) =???(n, d)n ²/d ² when ${1\,\leqslant\,d < n}$ . Let R _{k, n} be the number of reduced k ×?n Latin rectangles. We show that $$R_{k, n} \equiv \chi (p, n - p)\frac{(n - p)!(n - p - 1)!^{2}}{(n - k)!}R_{k-p,\,n-p}\,\,\,\,(\rm {mod}\,p)$$ when p is a prime and ${n\,\geqslant\,k\,\geqslant\,p + 1}$ . In particular, this enables us to calculate some previously unknown congruences for R _{n, n} . We also develop techniques for computing ??(n, d) exactly. We show that for each a there exists??? _a such that, on each congruence class modulo??? _a , ??(n, n-a) is determined by a polynomial of degree 2a in n. We give these polynomials for ${1\,\leqslant\,a\,\leqslant 6}$ , and find an asymptotic formula for ??(n, n-a) as n ?? ??, for arbitrary fixed a.     

Rademacher Inequalities with Applications

For symmetric operators B _i (B _i = ^d ?B _i ) and positive operators $A_{i}\succeq\tilde{A}_{i}$ , we compare moments of $\|B_{1}A_{1}^{p}+\cdots+B_{n}A_{n}^{p}\|$ and $\|B_{1}\tilde{A}_{1}^{p}+\cdots +B_{n}\tilde{A}_{n}^{p}\|$ .     

Moment multipliers for power series

По определению после довательность {μ _n пр инадлежит классуG _s , если звезда М иттагЛеффлера произвольного степе нного ряда (1) $$\mathop \sum \limits_0^\infty a_n z^n , \mathop {lim sup}\limits_{n \to \infty } \left| {a_n } \right|^{1/n}< \infty $$ , совпадает со звёздам и Миттаг-Леффлера сте пенных рядов $$\mathop \sum \limits_0^\infty \mu _n a_n z^n ,\mathop \sum \limits_0^\infty \mu _n^{ - 1} a_n z^n $$ . В работе установлены следующие утвержден ия Теорема 1.Для произво льной последователь ности ? _n с условиями $$0< \varphi _n< 1,\mathop {lim}\limits_{n \to \infty } \varphi _n = 0,\mathop {lim}\limits_{n \to \infty } \varphi _n^{1/n} = 1$$ существует неубываю щая функция χ(t) такая, ч то моменты \(\mu _n = \int\limits_0^1 {t^n d\chi (t)} \) удовлетворяют условию 0<μ_nn звезда М иттаг-Леффлера любог о ряда (1) совпадает со звездой МиттагЛеффлера степенных рядов . Теорема 2. Для произвол ьной неотрицательно й последовательности {а_n} с условием {a _n } и для любой последов ательности {?_n} для к оторой 0n<1, \(\mathop {\lim }\limits_{n \to \infty } \varepsilon _n = 0\) сущест вуютπ={π _n }∈G _s и последовательнос ть {п_i} такие, что a_nμ_n≦1 (n≧n₀), \(a_{n_i } \mu _{\mu _i } \geqq exp( - \varepsilon _{n_i } )\) (i=1, 2, ...) и при эmom звезда Миттаг-Леффлера ряда (1) совпа дает со звездой Миттаг- Леффлера степенных р ядов .     

Приближение всплесками и поперечники Фурье классов периодических функций многих переменных. II

Estimates sharp in order for Fourier widths of the classes $ B_{pq}^{sm} (\mathbb{T}^k ) $ and $ L_{pq}^{sm} (\mathbb{T}^k ) $ of Nikol??skii-Besov and Lizorkin-Triebel types, respectively, in the space $ L_r (\mathbb{T}^k ) $ are established for a certain range of the parameters s, p, q, r (here s ?? (0,??) ⁿ , 1 ??p, r, q ???, 1 ?? n ?? k, m = (m ₁, ??,m _n ) ?? ? ⁿ : m ₁ + ?? + m _n = k).     

Acyclic edge coloring of graphs with large girths

A proper edge coloring of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic chromatic index of G, denoted by χ’a(G), is the least number of colors such that G has an acyclic edge k-coloring. Let G be a graph with maximum degree Δ and girth g(G), and let 1≤r≤2Δ be an integer. In this paper, it is shown that there exists a constant c > 0 such that if g(G)≥cΔ r log(Δ2/r) then χa(G)≤Δ + r + 1, which generalizes the result of Alon et al. in 2001. When G is restricted to series-parallel graphs, it is proved that χ’a(G) = Δ if Δ≥4 and g(G)≥4; or Δ≥3 and g(G)≥5.     

Necessary and sufficient conditions for the asymptotic distribution of the largest entry of a sample correlation matrix

Let {X _k,i ; i ≥ 1, k ≥ 1} be a double array of nondegenerate i.i.d. random variables and let {p _n ; n ≥ 1} be a sequence of positive integers such that n/p _n is bounded away from 0 and ∞. In this paper we give the necessary and sufficient conditions for the asymptotic distribution of the largest entry ${L_{n}={\rm max}_{1\leq i < j\leq p_{n}}|\hat{\rho}^{(n)}_{i,j}|}$ of the sample correlation matrix ${{\bf {\Gamma}}_{n}=(\hat{\rho}_{i,j}^{(n)})_{1\leq i,j\leq p_{n}}}$ where ${\hat{\rho}^{(n)}_{i,j}}$ denotes the Pearson correlation coefficient between (X _1,i , ..., X _n,i )′ and (X _1,j ,...,X _n,j )′. Write ${F(x)= \mathbb{P}(|X_{1,1}|\leq x), x\geq0}$ , ${W_{c,n}={\rm max}_{1\leq i < j\leq p_{n}}|\sum_{k=1}^{n}(X_{k,i}-c)(X_{k,j}-c)|}$ , and ${W_{n}=W_{0,n},n\geq1,c\in(-\infty,\infty)}$ . Under the assumption that ${\mathbb{E}|X_{1,1}|^{2+\delta} < \infty}$ for some δ > 0, we show that the following six statements are equivalent: $$ {\bf (i)} \quad \lim_{n \to \infty} n^{2}\int\limits_{(n \log n)^{1/4}}^{\infty}\left( F^{n-1}(x) - F^{n-1}\left(\frac{\sqrt{n \log n}}{x}\right) \right) dF(x) = 0,$$ $$ {\bf (ii)}\quad n \mathbb{P}\left ( \max_{1 \leq i < j \leq n}|X_{1,i}X_{1,j} | \geq \sqrt{n \log n}\right ) \to 0 \quad{\rm as}\,n \to \infty,$$ $$ {\bf (iii)}\quad \frac{W_{\mu, n}}{\sqrt {n \log n}}\stackrel{\mathbb{P}}{\rightarrow} 2\sigma^{2},$$ $$ {\bf (iv)}\quad \left ( \frac{n}{\log n}\right )^{1/2} L_{n} \stackrel{\mathbb{P}}{\rightarrow} 2,$$ $$ {\bf (v)}\quad \lim_{n \rightarrow \infty}\mathbb{P}\left (\frac{W_{\mu, n}^{2}}{n \sigma^{4}} - a_{n}\leq t \right ) = \exp \left \{ - \frac{1}{\sqrt{8\pi}} e^{-t/2}\right \}, - \infty < t < \infty,$$ $$ {\bf (vi)}\quad \lim_{n \rightarrow \infty}\mathbb{P}\left (n L_{n}^{2} - a_{n}\leq t \right ) = \exp \left \{ - \frac{1}{\sqrt{8 \pi}} e^{-t/2}\right \}, - \infty < t < \infty$$ where ${\mu=\mathbb{E}X_{1,1}, \sigma^{2}=\mathbb{E}(X_{1,1} - \mu)^{2}}$ , and a _n  = 4 log p _n ? log log p _n . The equivalences between (i), (ii), (iii), and (v) assume that only ${\mathbb{E}X_{1,1}^{2} < \infty}$ . Weak laws of large numbers for W _n and L _n , n ≥  1, are also established and these are of the form ${W_{n}/n^{\alpha}\stackrel{\mathbb{P}}{\rightarrow} 0}\,(\alpha > 1/2)$ and ${n^{1-\alpha}L_{n}\stackrel{\mathbb{P}}{\rightarrow} 0}\,(1/2 < \alpha \leq 1)$ , respectively. The current work thus provides weak limit analogues of the strong limit theorems of Li and Rosalsky as well as a necessary and sufficient condition for the asymptotic distribution of L _n obtained by Jiang. Some open problems are also posed.     

On the odd harmonious graphs with applications

The necessary conditions for the existence of odd harmonious labelling of graph are obtained. A cycle C _n is odd harmonious if and only if n≡0 (mod 4). A complete graph K _n is odd harmonious if and only if n=2. A complete k-partite graph K(n ₁,n ₂,…,n _k ) is odd harmonious if and only if k=2. A windmill graph K _n ^t is odd harmonious if and only if n=2. The construction ways of odd harmonious graph are given. We prove that the graph ∨ _i=1 ⁿ G _i , the graph G(+r ₁,+r ₂,…,+r _p ), the graph $\bar{K_{m}}+_{0}P_{n}+_{e}\bar{K_{t}}$ , the graph G∪(X+∪ _k=1 ⁿ Y _k ), some trees and the product graph P _m ×P _n etc. are odd harmonious. The odd harmoniousness of graph can be used to solve undetermined equation.