A Larger Family of Planar Graphs that Satisfy the Total Coloring Conjecture

The article shrinks the Δ = 6 hole that exists in the family of planar graphs which satisfy the total coloring conjecture. Let G be a planar graph. If ${v_n^k}$ represents the number of vertices of degree n which lie on k distinct 3-cycles, for ${n, k \in \mathbb{N}}$ , then the conjecture is true for planar graphs which satisfy ${v_5^4 +2(v_5^{5^+} +v_6^4) +3v_6^5 +4v_6^{6^+} < 24}$ .     

Iterated Joining of Rooted Trees

For a given pair of trees T ₁, T ₂, two vertices ${v_1\in T_1}$ and ${v_2\in T_2}$ are said to be path-congruent if, for any integer k ≥ 1, the number p _k (v ₁) of paths contained in T ₁, of length k and passing through v ₁, equals the number p _k (v ₂) of paths contained in T ₂, of length k and passing through v ₂. We first provide polynomial constructions, and related examples, of pairs of non-isomorphic rooted trees ${T_{v_1}, T_{v_2}}$ with path-congruent roots v ₁, v ₂. Then we employ a joining operation between ${T_{v_1}, T_{v_2}}$ to get a tree J ₂ where v ₁, v ₂ do not necessarily belong to a maximal path. For any integer number m, the joining can be made such that the set {v ₁, v ₂} has distance m from the center Z(J ₂) of J ₂. By iterating the idea, an s-fold joining J _s can be considered, where the roots v ₁, . . . , v _s , s ≥ 2, are consecutive vertices of J _s . For s = 3 we give an explicit general construction where ${\{v_1, v_2, v_3\} \cap Z(J_3)=\emptyset}$ . On the other hand we prove that ${\{v_1,v_2,\ldots,v_s\} \cap Z(J_s)\neq\emptyset}$ for all s > 2, if ${T_{v_1}}$ and ${T_{v_s}}$ are isomorphic.     

Laplacian Spectral Radius and Maximum Degree of Trees with Perfect Matchings

Let μ(T) and Δ(T) denote the Laplacian spectral radius and the maximum degree of a tree T, respectively. Denote by ${\mathcal{T}_{2m}}$ the set of trees with perfect matchings on 2m vertices. In this paper, we show that for any ${T_1, T_2\in\mathcal{T}_{2m}}$ , if Δ(T ₁) > Δ(T ₂) and ${\Delta(T_1)\geq \lceil\frac{m}{2}\rceil+2}$ , then μ(T ₁) > μ(T ₂). By using this result, the first 20th largest trees in ${\mathcal{T}_{2m}}$ according to their Laplacian spectral radius are ordered. We also characterize the tree which alone minimizes (resp., maximizes) the Laplacian spectral radius among all the trees in ${\mathcal{T}_{2m}}$ with an arbitrary fixed maximum degree c (resp., when ${c \geq \lceil\frac{m}{2}\rceil + 1}$ ).     

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 local mountain pass type result for a system of nonlinear Schr?dinger equations

We consider a singular perturbation problem for a system of nonlinear Schr?dinger equations: $$ \begin{array}{l} -\varepsilon^2\Delta v_1 +V_1(x)v_1 = \mu_1 v_1^3 + \beta v_1v_2^2 \quad {\rm in}\,\,{\bf R}^N, \\ -\varepsilon^2\Delta v_2 +V_2(x)v_2 = \mu_2 v_2^3 + \beta v_1^2v_2 \quad {\rm in}\,\,{\bf R}^N, \\ \null\ v_1(x), \ v_2(x) >0 \quad {\rm in}\,\,{\bf R}^N, \\ \null\ v_1(x), \ v_2(x)\in H^1({\bf R}^N), \end{array} \quad\quad\quad\quad\quad (*) $$ where N?=?2, 3, ?? ₁, ?? ₂, ?? > 0 and V ₁(x), V ₂(x): R ^N ?? (0, ??) are positive continuous functions. We consider the case where the interaction ?? > 0 is relatively small and we define for ${P\in{\bf R}^N}$ the least energy level m(P) for non-trivial vector solutions of the rescaled ??limit?? problem: $$ \begin{array}{l} -\Delta v_1 +V_1(P)v_1 = \mu_1 v_1^3 + \beta v_1v_2^2 \quad {\rm in}\,\,{\bf R}^N, \\ -\Delta v_2 +V_2(P)v_2 = \mu_2 v_2^3 + \beta v_1^2v_2 \quad {\rm in}\,\,{\bf R}^N, \\ \null\ v_1(x), \ v_2(x) >0 \quad {\rm in}\,\,{\bf R}^N, \\ \null\ v_1(x), \ v_2(x)\in H^1({\bf R}^N). \end{array} \quad\quad\quad\quad\quad\quad (**) $$ We assume that there exists an open bounded set ${\Lambda\subset{\bf R}^N}$ satisfying $$ {\mathop {\rm inf} _{P\in\Lambda} m(P)} < {\mathop {\rm inf}_{P\in\partial\Lambda} m(P)}. $$ We show that (*) possesses a family of non-trivial vector positive solutions ${\{(v_{1\varepsilon}(x), v_{2\varepsilon} (x))\}_{\varepsilon\in (0,\varepsilon_0]}}$ which concentrates??after extracting a subsequence ?? _n ?? 0??to a point ${P_0\in\Lambda}$ with ${m(P_0)={\rm inf}_{P\in\Lambda}m(P)}$ . Moreover (v _1?? (x), v _2?? (x)) converges to a least energy non-trivial vector solution of (**) after a suitable rescaling.     

Forbidden Triples Containing a Complete Graph and a Complete Bipartite Graph of Small Order

For a graph G and a set \({\mathcal{F}}\) of connected graphs, G is said be \({\mathcal{F}}\) -free if G does not contain any member of \({\mathcal{F}}\) as an induced subgraph. We let \({\mathcal{G} _{3}(\mathcal{F})}\) denote the set of all 3-connected \({\mathcal{F}}\) -free graphs. This paper is concerned with sets \({\mathcal{F}}\) of connected graphs such that \({\mathcal{F}}\) contains no star, \({|\mathcal{F}|=3}\) and \({\mathcal{G}_{3}(\mathcal{F})}\) is finite. Among other results, we show that for a connected graph T( ≠ K ₁) which is not a star, \({\mathcal{G}_{3}(\{K_{4},K_{2,2},T\})}\) is finite if and only if T is a path of order at most 6.     

Random and algebraic permutations’ statistics

An algebraic permutation $\hat{A}\in S(N=n^{m})$ is the permutation of the N points of the finite torus ? _n ^m , realized by a linear operator A∈SL(m,? _n ). The statistical properties of algebraic permutations are quite different from those of random permutations of N points. For instance, the period length T(A) grows superexponentially with N for some (random) permutations A of N elements, whereas $T(\hat{A})$ is bounded by a power of N for algebraic permutations  $\hat{A}$ . The paper also contains a strange mean asymptotics formula for the number of points of the finite projective line P¹(? _n ) in terms of the zeta function.     

Trivectors yielding spreads in PG(5, 2)

Given an alternating trilinear form ${T\in {\rm Alt}(\times^{3}V_{6})}$ on V ₆ = V(6, 2) let ${\mathcal{L}_{T}}$ denote the set of those lines ${\langle a, b \rangle}$ in ${{\rm PG}(5,2)=\mathbb{P}V_{6}}$ which are T-singular, satisfying, that is, T(a, b, x) = 0 for all ${x\in {\rm PG}(5, 2).}$ If ${\mathcal{L}_{21}}$ is a Desarguesian line-spread in PG(5, 2) it is shown that ${\mathcal{L}_{T}=\mathcal{L}_{21}}$ for precisely three choices T ₁,T ₂,T ₃ of T, which moreover satisfy T ₁ + T ₂ + T ₃ = 0. For ${T\in\mathcal{T}:=\{T_{1},T_{2},T_{3}\}}$ the ${\mathcal{G}_{T}}$ -orbits of flats in PG(5, 2) are determined, where ${\mathcal{G}_{T}\cong {\rm SL}(3,4).2}$ denotes the stabilizer of T under the action of GL(6, 2). Further, for a representative U of each ${\mathcal{G}_{T}}$ -orbit, the T-associate U ^# is also determined, where by definition $$U^{\#}=\{v\in {\rm PG}(5,2)\, |\, T(u_{1},u_{2},v) = 0\, \,{\rm for\,all }\, \, u_{1},u_{2}\in U\}$$ .     

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.     

On the regular convergence of multiple series of numbers and multiple integrals of locally integrable functions over ℝ̄ + m

We investigate the regular convergence of the m-multiple series (*) $$\sum\limits_{j_1 = 0}^\infty {\sum\limits_{j_2 = 0}^\infty \cdots \sum\limits_{j_m = 0}^\infty {c_{j_1 ,j_2 } , \ldots j_m } }$$ of complex numbers, where m ≥ 2 is a fixed integer. We prove Fubini’s theorem in the discrete setting as follows. If the multiple series (*) converges regularly, then its sum in Pringsheim’s sense can also be computed by successive summation. We introduce and investigate the regular convergence of the m-multiple integral (**) $$\int_0^\infty {\int_0^\infty { \cdots \int_0^\infty {f\left( {t_1 ,t_2 , \ldots ,t_m } \right)dt_1 } } } dt_2 \cdots dt_m ,$$ where f : ?? ₊ ^m → ? is a locally integrable function in Lebesgue’s sense over the closed nonnegative octant ?? ₊ ^m := [0,∞) ^m . Our main result is a generalized version of Fubini’s theorem on successive integration formulated in Theorem 4.1 as follows. If f ∈ L _loc ¹ (?? ₊ ^m ), the multiple integral (**) converges regularly, and m = p + q, where p and q are positive integers, then the finite limit $$\mathop {\lim }\limits_{v_{_{p + 1} } , \cdots ,v_m \to \infty } \int_{u_1 }^{v_1 } {\int_{u_2 }^{v_2 } { \cdots \int_0^{v_{p + 1} } { \cdots \int_0^{v_m } {f\left( {t_1 ,t_2 , \ldots t_m } \right)dt_1 dt_2 } \cdots dt_m = :J\left( {u_1 ,v_1 ;u_2 v_2 ; \ldots ;u_p ,v_p } \right)} , 0 \leqslant u_k \leqslant v_k < \infty } ,k = 1,2, \ldots p,}$$ exists uniformly in each of its variables, and the finite limit $$\mathop {\lim }\limits_{v_1 ,v_2 \cdots ,v_p \to \infty } J\left( {0,v_1 ;0,v_2 ; \ldots ;0,v_p } \right) = I$$ also exists, where I is the limit of the multiple integral (**) in Pringsheim’s sense. The main results of this paper were announced without proofs in the Comptes Rendus Sci. Paris (see [8] in the References).     

Convergence of subdiagonal Padé approximations of C 0-semigroups

Let ${(r_{n})_{n \in \mathbb{N}}}$ be the sequence of subdiagonal Padé approximations of the exponential function. We prove that for ?A the generator of a uniformly bounded C ₀-semigroup T on a Banach space X, the sequence ${(r_{n}(-t A))_{n \in \mathbb{N}}}$ converges strongly to T(t) on D(A ^α ) for ${\alpha>\frac{1}{2}}$ . Local uniform convergence in t and explicit convergence rates in n are established. For specific classes of semigroups, such as bounded analytic or exponentially γ -stable ones, stronger estimates are proved. Finally, applications to the inversion of the vector-valued Laplace transform are given.     

Degree Sum Conditions for Cyclability in Bipartite Graphs

We denote by G[X, Y] a bipartite graph G with partite sets X and Y. Let d _G (v) be the degree of a vertex v in a graph G. For G[X, Y] and ${S \subseteq V(G),}$ we define ${\sigma_{1,1}(S):=\min\{d_G(x)+d_G(y) : (x,y) \in (X \cap S,Y) \cup (X, Y \cap S), xy \not\in E(G)\}}$ . Amar et al. (Opusc. Math. 29:345–364, 2009) obtained σ _1,1(S) condition for cyclability of balanced bipartite graphs. In this paper, we generalize the result as it includes the case of unbalanced bipartite graphs: if G[X, Y] is a 2-connected bipartite graph with |X| ≥ |Y| and ${S \subseteq V(G)}$ such that σ _1,1(S) ≥ |X| + 1, then either there exists a cycle containing S or ${|S \cap X| > |Y|}$ and there exists a cycle containing Y. This degree sum condition is sharp.     

On Families of Graphs of Large Cycle Indicator, Matrices of Large Order and Key Exchange Protocols With Nonlinear Polynomial Maps of Small Degree

This paper studies the group theoretical protocol of Diffie?CHellman key exchange in the case of symmetrical group ${S_{p^n}}$ and more general Cremona group ${C(\mathbb K^n)}$ of polynomial automorphisms of free module ${\mathbb K^n}$ over arbitrary commutative ring ${\mathbb K}$ . This algorithm depends very much on the choice of the base ${g_n \in C( \mathbb K^n)}$ . It is important to work with the base ${g_n \in C( \mathbb K^n)}$ , which is a polynomial map of a small degree and a large order such that the degrees of all powers ${g_n^k}$ are also bounded by a small constant. We suggest fast algorithms for generation of a map ${g_n={f_n} \xi_nf_n^{-1}}$ , where ?? _n is an affine transformation (degree is 1) of a large order and f _n is a fixed nonlinear polynomial map in n variables such that ${f_n^{-1}}$ is also a polynomial map and both maps f _n and ${f_n^{-1}}$ are of small degrees. The method is based on properties of infinite families of graphs with a large cycle indicator and families of graphs of a large girth in particular. It guaranties that the order of g _n is tending to infinity as the dimension n tends to infinity. We propose methods of fast generation of special families of cubical maps f _n such that ${f_n^{-1}}$ is also of degree 3 based on properties of families of graphs of a large girth and graphs with a large cycle indicator. At the end we discuss cryptographical applications of maps of the kind ?? f _n ??^?1 and some graph theoretical problems motivated by such applications.     

The Majorization Theorem for Signless Laplacian Spectral Radii of Connected Graphs

Let ${\pi=(d_{1},d_{2},\ldots,d_{n})}$ and ${\pi'=(d'_{1},d'_{2},\ldots,d'_{n})}$ be two non-increasing degree sequences. We say ${\pi}$ is majorizated by ${\pi'}$ , denoted by ${\pi \vartriangleleft \pi'}$ , if and only if ${\pi\neq \pi'}$ , ${\sum_{i=1}^{n}d_{i}=\sum_{i=1}^{n}d'_{i}}$ , and ${\sum_{i=1}^{j}d_{i}\leq\sum_{i=1}^{j}d'_{i}}$ for all ${j=1,2,\ldots,n}$ . If there exists one connected graph G with ${\pi}$ as its degree sequence and ${c=(\sum_{i=1}^{n}d_{i})/2-n+1}$ , then G is called a c-cyclic graph and ${\pi}$ is called a c-cyclic degree sequence. Suppose ${\pi}$ is a non-increasing c-cyclic degree sequence and ${\pi'}$ is a non-increasing graphic degree sequence, if ${\pi \vartriangleleft \pi'}$ and there exists some t ${(2\leq t\leq n)}$ such that ${d'_{t}\geq c+1}$ and ${d_{i}=d'_{i}}$ for all ${t+1\leq i\leq n}$ , then the majorization ${\pi \vartriangleleft \pi'}$ is called a normal majorization. Let μ(G) be the signless Laplacian spectral radius, i.e., the largest eigenvalue of the signless Laplacian matrix of G. We use C _π to denote the class of connected graphs with degree sequence π. If ${G \in C_{\pi}}$ and ${\mu(G)\geq \mu(G')}$ for any other ${G'\in C_{\pi}}$ , then we say G has greatest signless Laplacian radius in C _π . In this paper, we prove that: Let π and π′ be two different non-increasing c-cyclic (c ≥ 0) degree sequences, G and G′ be the connected c-cyclic graphs with greatest signless Laplacian spectral radii in C _π and C _π', respectively. If ${\pi \vartriangleleft \pi'}$ and it is a normal majorization, then ${\mu(G) < \mu(G')}$ . This result extends the main result of Zhang (Discrete Math 308:3143–3150, 2008).     

Circular law theorem for random Markov matrices

Let (X _jk ) _jk≥1 be i.i.d. nonnegative random variables with bounded density, mean m, and finite positive variance σ ². Let M be the n?× n random Markov matrix with i.i.d. rows defined by ${M_{jk}=X_{jk}/(X_{j1}+\cdots+X_{jn})}$ . In particular, when X ₁₁ follows an exponential law, the random matrix M belongs to the Dirichlet Markov Ensemble of random stochastic matrices. Let λ₁, . . . , λ _n be the eigenvalues of ${\sqrt{n}M}$ i.e. the roots in ${\mathbb{C}}$ of its characteristic polynomial. Our main result states that with probability one, the counting probability measure ${\frac{1}{n}\delta_{\lambda_1}+\cdots+\frac{1}{n}\delta_{\lambda_n}}$ converges weakly as n→∞ to the uniform law on the disk ${\{z\in\mathbb{C}:|z|\leq m^{-1}\sigma\}}$ . The bounded density assumption is purely technical and comes from the way we control the operator norm of the resolvent.     

A nonclassical law of the iterated logarithm for self-normalized partial sums

Let {X _n ,?n≧1} be a sequence of nondegenerate, symmetric, i.i.d. random variables which are in the domain of attraction of the normal?law?with zero means and possibly infinite variances. Denote ${S_{n}=\sum_{i=1}^{n} X_{i}}$ , ${V_{n}^{2}=\sum_{i=1}^{n} X_{i}^{2}}$ . Then we prove that there is a sequence of positive constants {b(n),?n≧1} which is defined by Klesov and Rosalsky [11], is monotonically approaching infinity and is not asymptotically equivalent to loglogn but is such that $\displaystyle \limsup_{n\to\infty} \frac{|S_n|}{\sqrt{2V_n^2b(n)}}= 1$ almost surely if some additional technical assumptions are imposed.     

Convolutions of random measures on compact groups

LetG be a compact group andM ₁(G) be the convolution semigroup of all Borel probability measures onG with the weak topology. We consider a stationary sequence {μ _n } _n=?∞ ^+∞ of random measures μ _n =μ _n (ω) inM ₁(G) and the convolutions $$v_{m,n} (\omega ) = \mu _m (\omega )* \cdots *\mu _{n - 1} (\omega ), m< n$$ and $$\alpha _n^{( + k)} (\omega ) = \frac{1}{k}\sum\limits_{i = 1}^k {v_{n,n + i} (\omega ),} \alpha _n^{( - k)} (\omega ) = \frac{1}{k}\sum\limits_{i = 1}^k {v_{n - i,n} (\omega )} $$ We describe the setsA _m ⁺ (ω) andA _n ⁺ (ω) of all limit points ofv _m,n(ω) asm→?∞ orn→+∞ and the setA _∞(ω) of its two-sided limit points for typical realizations of {μ _n (ω)} _n=?∞ ^+∞ . Using an appropriate random ergodic theorem we study the limit random measures ρ _n ^(±) (ω)=lim _k→∞ α _n ^(±k) (ω).     

Embedding height balanced trees and Fibonacci trees in hypercubes

A height balanced tree is a rooted binary tree T in which for every vertex v∈V(T), the difference b _T (v) between the heights of the subtrees, rooted at the left and right child of v is at most one. We show that a height-balanced tree T _h of height h is a subtree of the hypercube Q _h+1 of dimension h+1, if T _h contains a path P from its root to a leaf such that $\mathbf{b}_{T_{h}}(v)=1$ , for every non-leaf vertex v in P. A Fibonacci tree $\mathbb{F}_{h}$ is a height balanced tree T _h of height h in which $\mathbf{b}_{\mathbb{F}_{h}}(v)=1$ , for every non-leaf vertex. $\mathbb{F}_{h}$ has f(h+2)?1 vertices where f(h+2) denotes the (h+2)th Fibonacci number. Since f(h)～2^0.694h , it follows that if $\mathbb{F}_{h}$ is a subtree of Q _n , then n is at least 0.694(h+2). We prove that $\mathbb{F}_{h}$ is a subtree of the hypercube of dimension approximately 0.75h.     

Derived semidistributive lattices

For L a finite lattice, let ${\mathbb {C}(L) \subseteq L^2}$ denote the set of pairs γ = (γ ₀, γ ₁) such that ${\gamma_0 \prec \gamma_1}$ and order it as followsγ ≤ δ iff γ ₀ ≤ δ ₀, ${\gamma_{1} \nleq \delta_0,}$ and γ ₁ ≤ δ ₁. Let ${\mathbb {C}(L, \gamma)}$ denote the connected component of γ in this poset. Our main result states that, for any ${\gamma, \mathbb {C}(L, \gamma)}$ is a semidistributive lattice if L is semidistributive, and that ${\mathbb {C}(L, \gamma)}$ is a bounded lattice if L is bounded. Let ${\mathcal{S}_{n}}$ be the Permutohedron on n letters and let ${\mathcal{T}_{n}}$ be the Associahedron on n + 1 letters. Explicit computations show that ${\mathbb {C}(\mathcal{S}_{n}, \alpha) = \mathcal{S}_{n-1}}$ and ${\mathbb {C}(\mathcal {T}_n, \alpha) = \mathcal {T}_{n-1}}$ , up to isomorphism, whenever α1 is an atom of ${\mathcal{S}_{n}}$ or ${\mathcal{T}_{n}}$ . These results are consequences of new characterizations of finite join-semidistributive and of finite lower bounded lattices: (i) a finite lattice is join-semidistributive if and only if the projection sending ${\gamma \in \mathbb {C}(L)}$ to ${\gamma_0 \in L}$ creates pullbacks, (ii) a finite join-semidistributive lattice is lower bounded if and only if it has a strict facet labelling. Strict facet labellings, as defined here, are a generalization of the tools used by Caspard et al. to prove that lattices of finite Coxeter groups are bounded.