State complexity of power

The number of states in a deterministic finite automaton (DFA) recognizing the language $L^k$, where $L$ is regular language recognized by an $n$-state DFA, and $k?2$ is a constant, is shown to be at most $n{2}^{(k?1)n}$ and at least $(n?k)2^{(k?1)(n?k)}$ in the worst case, for every $n>k$ and for every alphabet of at least six letters. Thus, the state complexity of $L^k$ is $\Theta \left(n{2}^{(k?1)n}\right)$. In the case $k=3$ the corresponding state complexity function for $L^3$ is determined as $\frac{6n?3}{8}{4}^n?(n?1)2^n?n$ with the lower bound witnessed by automata over a four-letter alphabet. The nondeterministic state complexity of $L^k$ is demonstrated to be $nk$. This bound is shown to be tight over a two-letter alphabet.     

The Laplacian spectral radius of bicyclic graphs with a given girth

Let $?(n,g)$ be the class of bicyclic graphs on $n$ vertices with girth $g$. Let ${?}_1(n,g)$ be the subclass of $?(n,g)$ consisting of all bicyclic graphs with two edge-disjoint cycles and ${?}_2(n,g)=?(n,g)?{?}_1(n,g)$. This paper determines the unique graph with the maximal Laplacian spectral radius among all graphs in ${?}_1(n,g)$ and ${?}_2(n,g)$, respectively. Furthermore, the upper bound of the Laplacian spectral radius and the extremal graph for $?(n,g)$ are also obtained.     

Innovation based on Gaussian elimination to compute generalized inverse AT,S(2)

In this paper, we execute elementary row and column operations on the partitioned matrix $\left(\begin{array}{cc}\hfill GAG\hfill & \hfill G\hfill \\ \hfill G\hfill & \hfill 0\hfill \end{array}\right)$ into $\left(\begin{array}{cc}\hfill \left(\begin{array}{cc}\hfill I_s\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill \end{array}\right)\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill ?A_{T,S}^{\left(2\right)}\hfill \end{array}\right)$to compute generalized inverse $A_{T,S}^{\left(2\right)}$ of a given complex matrix $A$, where $G$ is a matrix such that $R\left(G\right)=T$ and $N\left(G\right)=S$. The total number of multiplications and divisions operations is $T(m,n,s)=2m{n}^2+\frac{4m?s?1}{2}ns+(m?s)ns+mns$ and the upper bound of $T(m,n,s)$ is less than $6m{n}^2?\frac{3}{2}{n}^3?\frac{1}{2}{n}^2$ when $n\le m$. A numerical example is shown to illustrate that this method is correct.     

Eigenvalues of a real supersymmetric tensor

In this paper, we define the symmetric hyperdeterminant, eigenvalues and E-eigenvalues of a real supersymmetric tensor. We show that eigenvalues are roots of a one-dimensional polynomial, and when the order of the tensor is even, E-eigenvalues are roots of another one-dimensional polynomial. These two one-dimensional polynomials are associated with the symmetric hyperdeterminant. We call them the characteristic polynomial and the E-characteristic polynomial of that supersymmetric tensor. Real eigenvalues (E-eigenvalues) with real eigenvectors (E-eigenvectors) are called H-eigenvalues (Z-eigenvalues). When the order of the supersymmetric tensor is even, H-eigenvalues (Z-eigenvalues) exist and the supersymmetric tensor is positive definite if and only if all of its H-eigenvalues (Z-eigenvalues) are positive. An $m\mathrm{th}$-order $n$-dimensional supersymmetric tensor where $m$ is even has exactly $n{(m-1)}^{n-1}$ eigenvalues, and the number of its E-eigenvalues is strictly less than $n{(m-1)}^{n-1}$ when $m\ge 4$. We show that the product of all the eigenvalues is equal to the value of the symmetric hyperdeterminant, while the sum of all the eigenvalues is equal to the sum of the diagonal elements of that supersymmetric tensor, multiplied by ${(m-1)}^{n-1}$. The $n{(m-1)}^{n-1}$ eigenvalues are distributed in $n$ disks in $C$. The centers and radii of these $n$ disks are the diagonal elements, and the sums of the absolute values of the corresponding off-diagonal elements, of that supersymmetric tensor. On the other hand, E-eigenvalues are invariant under orthogonal transformations.     

Trees with minimal Laplacian coefficients

Let $G$ be a simple undirected graph with the characteristic polynomial of its Laplacian matrix $L\left(G\right)$, $P(G,\mu )={\sum }_{k=0}^n{(?1)}^k{c}_k{\mu }^{n?k}$. It is well known that for trees the Laplacian coefficient $c_{n?2}$ is equal to the Wiener index of $G$, while $c_{n?3}$ is equal to the modified hyper-Wiener index of the graph. In this paper, we characterize $n$-vertex trees with given matching number $m$ which simultaneously minimize all Laplacian coefficients. The extremal tree $A(n,m)$ is a spur, obtained from the star graph $S_{n?m+1}$ with $n?m+1$ vertices by attaching a pendant edge to each of certain $m?1$ non-central vertices of $S_{n?m+1}$. In particular, $A(n,m)$ minimizes the Wiener index, the modified hyper-Wiener index and the recently introduced Incidence energy of trees, defined as $IE\left(G\right)={\sum }_{k=0}^n\sqrt{{\mu }_k}$, where ${\mu }_k$ are the eigenvalues of signless Laplacian matrix $Q\left(G\right)=D\left(G\right)+A\left(G\right)$. We introduced a general $\rho$ transformation which decreases all Laplacian coefficients simultaneously. In conclusion, we illustrate on examples of Wiener index and Incidence energy that the opposite problem of simultaneously maximizing all Laplacian coefficients has no solution.     

Finite time blow-up for a class of parabolic or pseudo-parabolic equations

In this paper, we study the initial boundary value problem for a class of parabolic or pseudo-parabolic equations:

$u_t?a\Delta u_t?\Delta u+bu=k\left(t\right)|u{|}^{p?2}u,(x,t)\in \Omega \times (0,T),$

where $a\ge 0$, $b>?{?}_1$ with ${?}_1$ being the principal eigenvalue for $?\Delta$ on $H_0^1\left(\Omega \right)$ and $k\left(t\right)>0$. By using the potential well method, Levine’s concavity method and some differential inequality techniques, we obtain the finite time blow-up results provided that the initial energy satisfies three conditions: (i) $J(u_0;0)<0$; (ii) $J(u_0;0)\le d\left(\infty \right)$, where $d\left(\infty \right)$ is a nonnegative constant; (iii) $0<J(u_0;0)\le C\rho \left(0\right)$, where $\rho \left(0\right)$ involves the $L^2$-norm or $H_0^1$-norm of the initial data. We also establish the lower and upper bounds for the blow-up time. In particular, we obtain the existence of certain solutions blowing up in finite time with initial data at the Nehari manifold or at arbitrary energy level.     

Best uniform polynomial approximation of some rational functions

In this research paper using the Chebyshev expansion, we explicitly determine the best uniform polynomial approximation out of $P_{qn}$ (the space of polynomials of degree at most $qn$) to a class of rational functions of the form $1/(T_q\left(a\right)\pm T_q\left(x\right))$ on $[?1,1]$, where $T_q\left(x\right)$ is the first kind of Chebyshev polynomial of degree $q$ and $a^2>1$. In this way we give some new theorems about the best approximation of this class of rational functions. Furthermore we obtain the alternating set of this class of functions.