A new neighborhood union condition for Hamiltonian graphs

For a vertex set {u ₁,u ₂,...,u _k} of a graphG withn vertices, let $$\begin{gathered} s(G;\{ u_1 ,u_2 ,...,u_k \} ) = \sum {1 \leqslant i< j \leqslant k\left| {N(u_i ) \cup N(u_j )} \right|,} \hfill \\ NC_k = \min \{ s(G;\{ x_1 ,...,x_k \} )\} :\{ x_1 ,...,x_k \} is an independent set\} . \hfill \\ \end{gathered} $$ In this paper, we shall prove that ifG is 3-connected andNC ₄≥3n, thenG is either a hamiltonian or Petersen graph. This generalizes some results on the neighborhood union conditions for hamiltonian graphs.     

Minimal decompositions of graphs into mutually isomorphic subgraphs

SupposeG _n={G ₁, ...,G _k } is a collection of graphs, all havingn vertices ande edges. By aU-decomposition ofG _n we mean a set of partitions of the edge setsE(G _t ) of theG _i , sayE(G _t )== \(\sum\limits_{j = 1}^r {E_{ij} } \) E _ij , such that for eachj, all theE _ij , 1≦i≦k, are isomorphic as graphs. Define the functionU(G _n) to be the least possible value ofr aU-decomposition ofG _n can have. Finally, letU _k (n) denote the largest possible valueU(G) can assume whereG ranges over all sets ofk graphs havingn vertices and the same (unspecified) number of edges. In an earlier paper, the authors showed that $$U_2 (n) = \frac{2}{3}n + o(n).$$ In this paper, the value ofU _k (n) is investigated fork>2. It turns out rather unexpectedly that the leading term ofU _k (n) does not depend onk. In particular we show $$U_k (n) = \frac{3}{4}n + o_k (n),k \geqq 3.$$      

On reconstructing separable reducedp-groups with a given socle

Let \(\bar B^* \) be a separable reduced (abelian)p-group which is torsion complete. We ask whether for \(G \subseteq \bar B^* \) there is \(H \subseteq _{pr} \bar B^* ,H[p] = G[p]\) ,H[p]=G[p],H not isomorphic toG. IfG is the sum of cyclic groups or is torsion complete, the answer is easily no. For otherG, we prove that the answer is yes assuming G.C.H. Even without G.C.H. the answer is yes if the density character ofG is equal to Min _n<ω|p ⁿG|, i.e., $$\mathop {Min}\limits_{n< \omega } |p^n G| = \mathop {Min}\limits_m \mathop \Sigma \limits_{n > m} |(p^n G)[p]/(p^{n + 1} G)[p]|$$ Of course, instead of two non-isomorphic we can get many, but we do not deal much with this.     

On integral graphs which belong to the class\overline {\alpha K_{a,a} \cup \beta {\rm K}_{b,b} }

LetG be a simple graph and letG denote its complement. We say thatG is integral if its spectrum consists of integral values. In this work we establish a characterization of integral graphs which belong to the class $\overline {\alpha K_{a,a} \cup \beta {\rm K}_{b,b} } $ wheremG denotes them-fold union of the graphG.     

Cops and Robber Game with a Fast Robber on Expander Graphs and Random Graphs

We consider a variant of the Cops and Robber game, in which the robber has unbounded speed, i.e., can take any path from her vertex in her turn, but she is not allowed to pass through a vertex occupied by a cop. Let ${c_{\infty}(G)}$ denote the number of cops needed to capture the robber in a graph G in this variant. We characterize graphs G with c _??(G) =? 1, and give an ${O( \mid V(G)\mid^2)}$ algorithm for their detection. We prove a lower bound for c _?? of expander graphs, and use it to prove three things. The first is that if ${np \geq 4.2 {\rm log}n}$ then the random graph ${G= \mathcal{G}(n, p)}$ asymptotically almost surely has ${\eta_{1}/p \leq \eta_{2}{\rm log}(np)/p}$ , for suitable positive constants ${\eta_{1}}$ and ${\eta_{2}}$ . The second is that a fixed-degree random regular graph G with n vertices asymptotically almost surely has ${c_{\infty}(G) = \Theta(n)}$ . The third is that if G is a Cartesian product of m paths, then ${n/4km^2 \leq c_{\infty}(G) \leq n/k}$ , where ${n = \mid V(G)\mid}$ and k is the number of vertices of the longest path.     

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 conjugate characteristic polynomial of a graph

Let $c=a+b\sqrt{m}$ and $\overline{c}=a-b\sqrt{m}$ , where a and b are two nonzero integers and m is a positive integer such that m is not a perfect square. We say that A ^c =[c _ij ] is the conjugate adjacency matrix of a graph G if c _ij =c for any two adjacent vertices i and j, $c_{ij}=\overline{c}$ for any two nonadjacent vertices i and j, and c _ij =0 if i=j. Let P _G ^c (λ)=|λ I?A ^c | denote the conjugate characteristic polynomial of G. Further, let e=e(G) and Δ=Δ(G) be the number of edges and number of triangles of G, respectively. Let G and H be two graphs of order n and let e(G)=e(H). In this work we prove that c ₃(G)=c ₃(H) if and only if Δ(G)=Δ(H) and $\Delta(\overline{G})=\Delta(\overline{H})$ , where $\overline{G}$ denotes the complement of G and c _k is the coefficient which corresponds to λ ^n?k with respect to P _G ^c (λ). Besides, we here give the conjugate spectrum and conjugate characteristic polynomial of all connected graphs of order n=2,3,4,5, with respect to the constant $c=1+\sqrt{2}$ .     

L 1 decay properties for a semilinear parabolic system

This article is concerned with the decay property in theL ¹ norm ast»∞ of the nonnegative solutions of the initial value problem in ? ⁿ $\left\{ {\begin{array}{*{20}c} {u_t = \Delta u + \mu |\nabla \upsilon |^q } \\ {\upsilon _t = \Delta \upsilon + \upsilon |\nabla \upsilon |^p } \\ \end{array} } \right.$ for different values of the parametersp, q≥1 and when μ, ν<0. If $pq > \frac{{\inf \left( {p,q} \right)}}{{n + 1}} + \left( {n + 2} \right)/\left( {n + 1} \right)$ then lim _t→∞∥u(t)+v(t)∥₁>0 and when $pq< \frac{{\inf \left( {p,q} \right)}}{{n + 1}} + \left( {n + 2} \right)/\left( {n + 1} \right)$ then lim _t→∞∥u(t)+v(t)∥₁>0.     

Rational approximations of real numbers

For anyx ∈ r put $$c(x) = \overline {\mathop {\lim }\limits_{t \to \infty } } \mathop {\min }\limits_{(p,q\mathop {) \in Z}\limits_{q \leqslant t} \times N} t\left| {qx - p} \right|.$$ . Let [x₀; x₁,..., x_n, ...] be an expansion of x into a continued fraction and let \(M = \{ x \in J,\overline {\mathop {\lim }\limits_{n \to \infty } } x_n< \infty \}\) .Forx∈M put D(x)=c(x)/(1?c(x)). The structure of the set \(\mathfrak{D} = \{ D(x),x \in M\}\) is studied. It is shown that $$\mathfrak{D} \cap (3 + \sqrt 3 ,(5 + 3\sqrt 3 )/2) = \{ D(x^{(n,3} )\} _{n = 0}^\infty \nearrow (5 + 3\sqrt 3 )/2,$$ where \(x^{(n,3)} = [\overline {3;(1,2)_n ,1} ].\) This yields for \(\mu = \inf \{ z,\mathfrak{D} \supset (z, + \infty )\}\) (“origin of the ray”) the following lower bound: μ?(5+3√3)/2=5.0n>(5 + 3/3)/2=5.098.... Suppose a∈n. Put \(M(a) = \{ x \in M,\overline {\mathop {\lim }\limits_{n \to \infty } } x_n = a\}\) , \(\mathfrak{D}(a) = \{ D(x),x \in M(a)\}\) . The smallest limit point of \(\mathfrak{D}(a)(a \geqslant 2)\) is found. The structure of (a) is studied completely up to the smallest limit point and elucidated to the right of it.     

The t-Tone Chromatic Number of Random Graphs

A proper 2-tone k-coloring of a graph is a labeling of the vertices with elements from \({\binom{[k]}{2}}\) such that adjacent vertices receive disjoint labels and vertices distance 2 apart receive distinct labels. The 2-tone chromatic number of a graph G, denoted τ ₂(G) is the smallest k such that G admits a proper 2-tone k coloring. In this paper, we prove that w.h.p. for \({p\geq Cn^{-1/4} {\rm ln}^{9/4}n, \tau_2(G_{n, p}) = (2 + o(1))\chi(G_{n, p})}\) where \({\chi}\) represents the ordinary chromatic number. For sparse random graphs with p = c/n, c constant, we prove that \({\tau_2(G_{n, p}) = \lceil{({\sqrt{8\Delta + 1} + 5})/{2}}}\) where Δ represents the maximum degree. For the more general concept of t-tone coloring, we achieve similar results.     

A law of the iterated logarithm for random walk in random scenery with deterministic normalizers

LetX, X _i ,i≥1, be a sequence of independent and identically distributed ? ^d -valued random vectors. LetS _o=0 and \(S_n = \sum\nolimits_{i = 1}^n {X_i } \) forn≤1. Furthermore letY, Y(α), α∈? ^d , be independent and identically distributed ?-valued random variables, which are independent of theX _i . Let \(Z_n = \sum\nolimits_{i = 0}^n {Y(S_i )} \) . We will call (Z _n ) arandom walk in random scenery. In this paper, we consider the law of the iterated logarithm for random walk in random scenery where deterministic normalizers are utilized. For example, we show that if (S _n ) is simple, symmetric random walk in the plane,E[Y]=0 andE[Y ²]=1, then $$\mathop {\overline {\lim } }\limits_{n \to \infty } \frac{{Z_n }}{{\sqrt {2n\log (n)\log (\log (n))} }} = \sqrt {\frac{2}{\pi }} a.s.$$      

An abstract Dirichlet problem in the Hilbert space

In the present paper, we consider an abstract partial differential equation of the form $\frac{{\partial ^2 u}}{{\partial t^2 }} - \frac{{\partial ^2 u}}{{\partial x^2 }} + A\left( {x,t} \right)u = f\left( {x,t} \right)$ , where $\left\{ {A\left( {x,t} \right):\left( {x,t} \right) \in \bar G} \right\}$ is a family of linear closed operators and $\bar G = G \cup \partial G,G$ is a suitable bounded region in the (x, t)-plane with boundary?G. It is assumed thatu is given on the boundary?G. The objective of this paper is to study the considered Dirichlet problem for a wide class of operatorsA(x, t). A Dirichlet problem for non-elliptic partial differential equations of higher orders is also considered.     

Symmetric diameter two graphs with affine-type vertex-quasiprimitive automorphism group

We study the class of G-symmetric graphs Γ with diameter 2, where G is an affine-type quasiprimitive group on the vertex set of Γ. These graphs arise from normal quotient analysis as basic graphs in the class of symmetric diameter 2 graphs. It is known that ${G \cong V \rtimes G_0}$ , where V is a finite-dimensional vector space over a finite field and G ₀ is an irreducible subgroup of GL (V), and Γ is a Cayley graph on V. In particular, we consider the case where ${V = \mathbb {F}_p^d}$ for some prime p and G ₀ is maximal in GL (d, p), with G ₀ belonging to the Aschbacher classes ${\mathcal {C}_2, \mathcal {C}_4, \mathcal {C}_6, \mathcal {C}_7}$ , and ${\mathcal {C}_8}$ . For ${G_0 \in \mathcal {C}_i, i = 2,4,8}$ , we determine all diameter 2 graphs which arise. For ${G_0 \in \mathcal {C}_6, \mathcal {C}_7}$ we obtain necessary conditions for diameter 2, which restrict the number of unresolved cases to be investigated, and in some special cases determine all diameter 2 graphs.     

A relationship between bounds on the sum of squares of degrees of a graph

LetG = (V, E) be a simple graph withn vertices and e edges. Letdi be the degree of the ith vertex v_i ∈ V andm _i the average of the degrees of the vertices adjacent to vertexv _i ∈ V. It is known by Caen [1] and Das [2] that $\frac{{4e^2 }}{n} \leqslant d_1^2 + ... + d_n^2 \leqslant e max \{ d_j + m_j |v_j \in V\} \leqslant e\left( {\frac{{2e}}{{n - 1}} + n - 2} \right)$ . In general, the equalities do not hold in above inequality. It is shown that a graphG is regular if and only if $\frac{{4e^2 }}{n} = d_1^2 + ... + d_n^2 $ . In fact, it is shown a little bit more strong result that a graphG is regular if and only if $\frac{{4e^2 }}{n} = d_1^2 + ... + d_n^2 = e max \{ d_j + m_j |v_j \in V\} $ . For a graphG withn < 2 vertices, it is shown that G is a complete graphK _n if and only if $\frac{{4e^2 }}{n} = d_1^2 + ... + d_n^2 = e max \{ d_j + m_j |v_j \in V\} = e\left( {\frac{{2e}}{{n - 1}} + n - 2} \right)$ .     

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).     

The Signed Edge-Domatic Number of a Graph

For a nonempty graph G = (V, E), a signed edge-domination of G is a function ${f: E(G) \to \{1,-1\}}$ such that ${\sum_{e'\in N_{G}[e]}{f(e')} \geq 1}$ for each ${e \in E(G)}$ . The signed edge-domatic number of G is the largest integer d for which there is a set {f ₁,f ₂, . . . , f _d } of signed edge-dominations of G such that ${\sum_{i=1}^{d}{f_i(e)} \leq 1}$ for every ${e \in E(G)}$ . This paper gives an original study on this concept and determines exact values for some special classes of graphs, such as paths, cycles, stars, fans, grids, and complete graphs with even order.     

Convergence of the Vallée-Poussin means for Fourier-Jacobi sums

Letf εC[?1, 1], ?1<α,β≤0, let $f \in C[ - 1, 1], - 1< \alpha , \beta \leqslant 0$ , letS _n ^{α, β} (f, x) be a partial Fourier-Jacobi sum of ordern, and let $$\nu _{m, n}^{\alpha , \beta } = \nu _{m, n}^{\alpha , \beta } (f) = \nu _{m, n}^{\alpha , \beta } (f,x) = \frac{1}{{n + 1}}[S_m^{\alpha ,\beta } (f,x) + ... + S_{m + n}^{\alpha ,\beta } (f,x)]$$ be the Vallée-Poussin means for Fourier-Jacobi sums. It was proved that if 0<a≤m/n≤b, then there exists a constantc=c(α, β, a, b) such that ‖ν _{m, n} ^{α, β} ‖ ≤c, where ‖ν _{m, n} ^{α, β} ‖ is the norm of the operator ν _{m, n} ^{α, β} inC[?1,1].     

Some results on starlike trees and sunlike graphs

A tree is called starlike if it has exactly one vertex of degree greater than two. In [4] it was proved that two starlike treesG andH are cospectral if and only if they are isomorphic. We prove here that there exist no two non-isomorphic Laplacian cospectral starlike trees. Further, letG be a simple graph of ordern with vertex setV(G)={1,2, …,n} and letH={H ₁,H ₂, ...H _n } be a family of rooted graphs. According to [2], the rooted productG(H) is the graph obtained by identifying the root ofH _i with thei-th vertex ofG. In particular, ifH is the family of the paths $P_{k_1 } , P_{k_2 } , ..., P_{k_n } $ with the rooted vertices of degree one, in this paper the corresponding graphG(H) is called the sunlike graph and is denoted byG(k ₁,k ₂, …,k _n ). For any (x ₁,x ₂, …,x _n ) ∈I _* ⁿ , whereI _*={0,1}, letG(x ₁,x ₂, …,x _n ) be the subgraph ofG which is obtained by deleting the verticesi ₁, i₂, …,i _j ∈ V(G) (0≤j≤n), provided that $x_{i_1 } = x_{i_2 } = ... = x_{i_j } = 0$ . LetG(x ₁,x ₂,…, x _n] be the characteristic polynomial ofG(x ₁,x ₂,…, x _n ), understanding thatG[0, 0, …, 0] ≡ 1. We prove that $$G[k_1 , k_2 ,..., k_n ] = \Sigma _{x \in ^{I_ * ^n } } \left[ {\Pi _{i = 1}^n P_{k_i + x_i - 2} (\lambda )} \right]( - 1)^{n - (\mathop \Sigma \limits_{i = 1}^n x_i )} G[x_1 , x_2 , ..., x_n ]$$ where x=(x ₁,x ₂,…,x _n );G[k ₁,k ₂,…,k _n ] andP _n (γ) denote the characteristic polynomial ofG(k ₁,k ₂,…,k _n ) andP _n , respectively. Besides, ifG is a graph with λ₁(G)≥1 we show that λ₁(G)≤λ₁(G(k ₁,k ₂, ...,k _n )) < for all positive integersk ₁,k ₂,…,k _n , where λ₁ denotes the largest eigenvalue.     

The Linear t-Colorings of Sierpiński-Like Graphs

A proper t-coloring of a graph G is a mapping ${\varphi: V(G) \rightarrow [1, t]}$ such that ${\varphi(u) \neq \varphi(v)}$ if u and v are adjacent vertices, where t is a positive integer. The chromatic number of a graph G, denoted by ${\chi(G)}$ , is the minimum number of colors required in any proper coloring of G. A linear t-coloring of a graph is a proper t-coloring such that the graph induced by the vertices of any two color classes is the union of vertex-disjoint paths. The linear chromatic number of a graph G, denoted by ${lc(G)}$ , is the minimum t such that G has a linear t-coloring. In this paper, the linear t-colorings of Sierpiński-like graphs S(n, k), ${S^+(n, k)}$ and ${S^{++}(n, k)}$ are studied. It is obtained that ${lc(S(n, k))= \chi (S(n, k)) = k}$ for any positive integers n and k, ${lc(S^+(n, k)) = \chi(S^+(n, k)) = k}$ and ${lc(S^{++}(n, k)) = \chi(S^{++}(n, k)) = k}$ for any positive integers ${n \geq 2}$ and ${k \geq 3}$ . Furthermore, we have determined the number of paths and the length of each path in the subgraph induced by the union of any two color classes completely.     

Packing an equilateral polygon in a thin strip

LetP _m denote an equilateral polygon ofm sides with each side having length 1 and we allow the sides to cross and vertex repetitions. We consider the following question. What is the smallest widtht _m of a horizontal strip in the Euclidean plane that contains aP _m ? This problem has its origins in Euclidean Ramsey theory. Whenm is even, it is easy to see thatt _m =0. For a polygon with an odd number of sides, we prove that $\begin{gathered} t_{2n + 1} = \frac{{\sqrt {2n + 1} }}{{n + 1}} for 2n + 1 \equiv 3(\bmod 4) and \hfill \\ t_{2n + 1} = \sqrt {\frac{{2n + 1}}{{n^2 + 2n}}} for 2n + 1 \equiv 1(\bmod 4) \hfill \\ \end{gathered} $ respectively. Applying the result to unit distance graphs, we prove the following: SupposeG is a unit-distance graph, i.e.G can be drawn on the planeR ² such that each edge ofG is a straight line segment of length 1. IfG has no odd circuits of length greater than or equal to 15, thenX(G) ≤ 6, whereX(G) is the chromatic number ofG.