Proof of a conjecture of V. Nikiforov

Using analytical tools, we prove that for any simple graph G on n vertices and its complement [`(G)]\bar G the inequality $\mu \left( G \right) + \mu \left( {\bar G} \right) \leqslant \tfrac{4} {3}n - 1$\mu \left( G \right) + \mu \left( {\bar G} \right) \leqslant \tfrac{4} {3}n - 1 holds, where μ(G) and m( [`(G)] )\mu \left( {\bar G} \right) denote the greatest eigenvalue of adjacency matrix of the graphs G and [`(G)]\bar G respectively.     

On Bernstein–Walsh-type lemmas in regions of the complex plane

Let G ì \mathbb C G \subset {\mathbb C} be a finite region bounded by a Jordan curve L: = ?G L: = \partial G , let W: = \textext[`(G)] \Omega : = {\text{ext}}\bar{G} (with respect to [`(\mathbb C)] {\overline {\mathbb C}} ), $ \Delta : = \left\{ {z:\left| z \right| > 1} \right\} $ \Delta : = \left\{ {z:\left| z \right| > 1} \right\} , and let w = F(z) w = \Phi (z) be a univalent conformal mapping of Ω onto Δ normalized by $ \Phi \left( \infty \right) = \infty, \;\Phi '\left( \infty \right) > 0 $ \Phi \left( \infty \right) = \infty, \;\Phi '\left( \infty \right) > 0 . By A _p (G); p > 0; we denote a class of functions f analytic in G and satisfying the condition

On minimal p-degrees in 2-transitive permutation groups

Suppose G is a transitive permutation group on a finite set W\mit\Omega of n points and let p be a prime divisor of |G||G|. The smallest number of points moved by a non-identity p-element is called the minimal p-degree of G and is denoted m_p (G). ¶ In the article the minimal p-degrees of various 2-transitive permutation groups are calculated. Using the classification of finite 2-transitive permutation groups these results yield the main theorem, that m_p(G) 3 [(p-1)/(p+1)] ·|W|m_{p}(G) \geq {{p-1} \over {p+1}} \cdot |\mit\Omega | holds, if Alt(W) \nleqq G {\rm Alt}(\mit\Omega ) \nleqq G .¶Also all groups G (and prime divisors p of |G||G|) for which m_p(G) ￡ [(p-1)/(p)] ·|W|m_{p}(G)\le {{p-1}\over{p}} \cdot |\mit\Omega | are identified.     

Pan-connectedness of graphs with large neighborhood unions

Let G be a simple graph with n vertices. For any v ? V(G){v \in V(G)} , let N(v)={u ? V(G): uv ? E(G)}{N(v)=\{u \in V(G): uv \in E(G)\}} , NC(G) = min{|N(u) èN(v)|: u, v ? V(G){NC(G)= \min \{|N(u) \cup N(v)|: u, v \in V(G)} and uv \not ? E(G)}{uv \not \in E(G)\}} , and NC₂(G) = min{|N(u) èN(v)|: u, v ? V(G){NC_2(G)= \min\{|N(u) \cup N(v)|: u, v \in V(G)} and u and v has distance 2 in E(G)}. Let l ≥ 1 be an integer. A graph G on n ≥ l vertices is [l, n]-pan-connected if for any u, v ? V(G){u, v \in V(G)} , and any integer m with l ≤ m ≤ n, G has a (u, v)-path of length m. In 1998, Wei and Zhu (Graphs Combinatorics 14:263–274, 1998) proved that for a three-connected graph on n ≥ 7 vertices, if NC(G) ≥ n − δ(G) + 1, then G is [6, n]-pan-connected. They conjectured that such graphs should be [5, n]-pan-connected. In this paper, we prove that for a three-connected graph on n ≥ 7 vertices, if NC ₂(G) ≥ n − δ(G) + 1, then G is [5, n]-pan-connected. Consequently, the conjecture of Wei and Zhu is proved as NC ₂(G) ≥ NC(G). Furthermore, we show that the lower bound is best possible and characterize all 2-connected graphs with NC ₂(G) ≥ n − δ(G) + 1 which are not [4, n]-pan-connected.     

Vertex-Distinguishing Edge Colorings of Graphs with Degree Sum Conditions

An edge coloring is called vertex-distinguishing if every two distinct vertices are incident to different sets of colored edges. The minimum number of colors required for a vertex-distinguishing proper edge coloring of a simple graph G is denoted by c￠_vd(G){\chi'_{vd}(G)}. It is proved that c￠_vd(G) ￡ D(G)+5{\chi'_{vd}(G)\leq\Delta(G)+5} if G is a connected graph of order n ≥ 3 and s₂(G) 3 \frac2n3{\sigma_{2}(G)\geq\frac{2n}{3}}, where σ ₂(G) denotes the minimum degree sum of two nonadjacent vertices in G.     

Color Chain of a Graph

For a simple connected undirected graph G, c(G), c_f(G), Y_f(G), f(G), ?G(G){\chi(G), \chi_f(G), \Psi_f(G), \phi(G), \partial \Gamma (G)} and Ψ(G) denote respectively the chromatic number, fall chromatic number (assuming that it exists for G), fall achromatic number, b-chromatic number, partial Grundy number and achromatic number of G. It is shown in Dunbar et al. (J Combin Math & Combin Comput 33:257–273, 2000) that for any graph G for which fall coloring exists, c(G) ￡ c_f(G) ￡ Y_f (G) ￡ f(G) ￡ ?G(G) ￡ Y(G){\chi (G)\leq \chi_f(G) \leq \Psi_f (G) \leq \phi(G) \leq \partial \Gamma (G)\leq \Psi (G)} . In this paper, we exhibit an infinite family of graphs G with a strictly increasing color chain: c(G) < c_f(G) < Y_f (G) < f(G) < ?G(G) < Y(G){\chi (G) < \chi_f(G) < \Psi_f (G) < \phi(G) < \partial \Gamma (G) < \Psi (G)} . The existence of such a chain was raised by Dunbar et al.     

Roman domination subdivision number of graphs

A Roman dominating function on a graph G = (V, E) is a function f : V ? {0, 1, 2}f : V \rightarrow \{0, 1, 2\} satisfying the condition that every vertex v for which f(v) = 0 is adjacent to at least one vertex u for which f(u) = 2. The weight of a Roman dominating function is the value w(f) = ?_{v ? V} f(v)w(f) = \sum_{v\in V} f(v). The Roman domination number of a graph G, denoted by _gR(G)_{\gamma R}(G), equals the minimum weight of a Roman dominating function on G. The Roman domination subdivision number sd_gR(G)sd_{\gamma R}(G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the Roman domination number. In this paper, first we establish upper bounds on the Roman domination subdivision number for arbitrary graphs in terms of vertex degree. Then we present several different conditions on G which are sufficient to imply that $1 \leq sd_{\gamma R}(G) \leq 3$1 \leq sd_{\gamma R}(G) \leq 3. Finally, we show that the Roman domination subdivision number of a graph can be arbitrarily large.     

Analysis of the impact of the number of edges in connected graphs on the computational complexity of the independent set problem

Under study is the complexity status of the independent set problem in a class of connected graphs that are defined by functional constraints on the number of edges depending on the number of vertices. For every natural number C, this problem is shown to be polynomially solvable in the class of graphs

A new characterization for some linear groups

Let G be a group and π _e (G) be the set of element orders of G. Let k ? p_e(G){k\in\pi_e(G)} and m _k be the number of elements of order k in G. Let nse(G) = {m_k|k ? p_e(G)}{{\rm nse}(G) = \{m_k|k\in\pi_e(G)\}} . In Shen et al. (Monatsh Math, 2009), the authors proved that A₄ @ PSL(2, 3), A₅ @ PSL(2, 4) @ PSL(2,5){A_4\cong {\rm PSL}(2, 3), A_5\cong \rm{PSL}(2, 4)\cong \rm{PSL}(2,5)} and A₆ @ PSL(2,9){A_6\cong \rm{PSL}(2,9)} are uniquely determined by nse(G). In this paper, we prove that if G is a group such that nse(G) = nse(PSL(2, q)), where q ? {7,8,11,13}{q\in\{7,8,11,13\}} , then G @ PSL(2,q){G\cong {PSL}(2,q)} .     

Extinction of solutions of semilinear higher order parabolic equations with degenerate absorption potential

We study the first vanishing time for solutions of the Cauchy–Dirichlet problem for the 2m-order (m ≥ 1) semilinear parabolic equation ${u_t + Lu + a(x) |u|^{q-1}u=0,\,0 < q < 1}We study the first vanishing time for solutions of the Cauchy–Dirichlet problem for the 2m-order (m ≥ 1) semilinear parabolic equation u_t + Lu + a(x) |u|^q-1u=0, 0 < q < 1{u_t + Lu + a(x) |u|^{q-1}u=0,\,0 < q < 1} with a(x) ≥ 0 bounded in the bounded domain W ì \mathbb R^N{\Omega \subset \mathbb R^N}. We prove that if N 1 2m{N \ne 2m} and ò₀¹ s^-1 (meas\nolimits {x ? W: |a(x)| ￡ s })^q ds < ￥, q = min(\frac2mN,1){\int_0^1 s^{-1} (\mathop{\rm meas}\nolimits \{x \in \Omega : |a(x)| \leq s \})^\theta {\rm d}s < \infty,\ \theta=\min\left(\frac{2m}N,1\right)}, then the solution u vanishes in a finite time. When N = 2m, the same property holds if ${\int_0^1 s^{-1} \left( \mathop{\rm meas}\nolimits \{x \in \Omega : |a(x)| \leq s \} \right) \ln \left( \mathop{\rm meas}\nolimits \{x \in \Omega : |a(x)| \leq s \} \right) {\rm d}s > - \infty}${\int_0^1 s^{-1} \left( \mathop{\rm meas}\nolimits \{x \in \Omega : |a(x)| \leq s \} \right) \ln \left( \mathop{\rm meas}\nolimits \{x \in \Omega : |a(x)| \leq s \} \right) {\rm d}s > - \infty}.     

Collapsible Graphs and Hamiltonicity of Line Graphs

Thomassen conjectured that every 4-connected line graph is Hamiltonian. Chen and Lai (Combinatorics and Graph Theory, vol 95, World Scientific, Singapore, pp 53–69; Conjecture 8.6 of 1995) conjectured that every 3-edge connected and essentially 6-edge connected graph is collapsible. Denote D ₃(G) the set of vertices of degree 3 of graph G. For ${e = uv \in E(G)}$ , define d(e) = d(u) + d(v) ? 2 the edge degree of e, and ${\xi(G) = \min\{d(e) : e \in E(G)\}}$ . Denote by λ ^m (G) the m-restricted edge-connectivity of G. In this paper, we prove that a 3-edge-connected graph with ${\xi(G)\geq7}$ , and ${\lambda^3(G)\geq7}$ is collapsible; a 3-edge-connected simple graph with ${\xi(G)\geq7}$ , and ${\lambda^3(G)\geq6}$ is collapsible; a 3-edge-connected graph with ${\xi(G)\geq6}$ , ${\lambda^2(G)\geq4}$ , and ${\lambda^3(G)\geq6}$ with at most 24 vertices of degree 3 is collapsible; a 3-edge-connected simple graph with ${\xi(G)\geq6}$ , and ${\lambda^3(G)\geq5}$ with at most 24 vertices of degree 3 is collapsible; a 3-edge-connected graph with ${\xi(G)\geq5}$ , and ${\lambda^2(G)\geq4}$ with at most 9 vertices of degree 3 is collapsible. As a corollary, we show that a 4-connected line graph L(G) with minimum degree at least 5 and ${|D_3(G)|\leq9}$ is Hamiltonian.     

Lower bounds on the number of maximal subgroups in a finite group

For a finite group G, let m(G) denote the set of maximal subgroups of G and π(G) denote the set of primes which divide |G|. When G is a cyclic group, an elementary calculation proves that |m(G)| = |π(G)|. In this paper, we prove lower bounds on |m(G)| when G is not cyclic. In general, ${|m(G)| \geq |\pi(G)|+p}$ | m ( G ) | ≥ | π ( G ) | + p , where ${p \in \pi(G)}$ p ∈ π ( G ) is the smallest prime that divides |G|. If G has a noncyclic Sylow subgroup and ${q \in \pi(G)}$ q ∈ π ( G ) is the smallest prime such that ${Q \in {\rm syl}_q(G)}$ Q ∈ syl q ( G ) is noncyclic, then ${|m(G)| \geq |\pi(G)|+q}$ | m ( G ) | ≥ | π ( G ) | + q . Both lower bounds are best possible.     

Boxicity of Circular Arc Graphs

A k-dimensional box is a Cartesian product R ₁ × · · · × R _k where each R _i is a closed interval on the real line. The boxicity of a graph G, denoted as box(G), is the minimum integer k such that G can be represented as the intersection graph of a collection of k-dimensional boxes. That is, two vertices are adjacent if and only if their corresponding boxes intersect. A circular arc graph is a graph that can be represented as the intersection graph of arcs on a circle. We show that if G is a circular arc graph which admits a circular arc representation in which no arc has length at least p(\fraca-1a){\pi(\frac{\alpha-1}{\alpha})} for some a ? \mathbbN _{3 2}{\alpha\in\mathbb{N}_{\geq 2}}, then box(G) ≤ α (Here the arcs are considered with respect to a unit circle). From this result we show that if G has maximum degree D < ?\fracn(a-1)2a?{\Delta < \lfloor{\frac{n(\alpha-1)}{2\alpha}}\rfloor} for some a ? \mathbbN _{3 2}{\alpha \in \mathbb{N}_{\geq 2}}, then box(G) ≤ α. We also demonstrate a graph having box(G) > α but with D = n\frac(a-1)2a+ \fracn2a(a+1)+(a+2){\Delta=n\frac{(\alpha-1)}{2\alpha}+ \frac{n}{2\alpha(\alpha+1)}+(\alpha+2)}. For a proper circular arc graph G, we show that if D < ?\fracn(a-1)a?{\Delta < \lfloor{\frac{n(\alpha-1)}{\alpha}}\rfloor} for some a ? \mathbbN _{3 2}{\alpha\in \mathbb{N}_{\geq 2}}, then box(G) ≤ α. Let r be the cardinality of the minimum overlap set, i.e. the minimum number of arcs passing through any point on the circle, with respect to some circular arc representation of G. We show that for any circular arc graph G, box(G) ≤ r + 1 and this bound is tight. We show that if G admits a circular arc representation in which no family of k ≤ 3 arcs covers the circle, then box(G) ≤ 3 and if G admits a circular arc representation in which no family of k ≤ 4 arcs covers the circle, then box(G) ≤ 2. We also show that both these bounds are tight.     

The Edge Correlation of Random Forests

The conjecture was made by Kahn that a spanning forest F chosen uniformly at random from all forests of any finite graph G has the edge-negative association property. If true, the conjecture would mean that given any two edges ε₁ and ε₂ in G, the inequality \mathbbP(e₁ ? F, e₂ ? F) ￡ \mathbbP(e₁ ? F)\mathbbP(e₂ ? F){{\mathbb{P}(\varepsilon_{1} \in \mathbf{F}, \varepsilon_{2} \in \mathbf{F}) \leq \mathbb{P}(\varepsilon_{1} \in \mathbf{F})\mathbb{P}(\varepsilon_{2} \in \mathbf{F})}} would hold. We use enumerative methods to show that this conjecture is true for n large enough when G is a complete graph on n vertices. We derive explicit related results for random trees.     

On the selfsimilar solutions of a diffusion convection equation

This paper is concerned with the equation¶¶ div(| ?u| ^p-2?u)+e| ?U| ^q+bx?U+aU=0, for  x ? \mathbbR^N div(| \nabla u| ^{p-2}\nabla u)+\varepsilon \left| \nabla U\right| ^q+\beta x\nabla U+\alpha U=0,{\rm \ for}\;x\in \mathbb{R}^N ¶¶ where $ p>2,\;q\geq 1,\;N\geq 1, \quad\varepsilon =\pm 1 $ p>2,\;q\geq 1,\;N\geq 1, \quad\varepsilon =\pm 1 and a,b, m \alpha ,\beta, \mu are positive parameters. We study the existence, uniqueness of radial solutions u(r). Also, qualitative behavior of u(r) are presented.     

Domination numbers of undirected toroidal mesh

The (d, m)-domination number γd,m is a new measure to characterize the reliability of resources-sharing in fault tolerant networks, in some sense, which can more accurately characterize the reliability of networks than the m-diameter does. In this paper, we study the (d, 4)-domination numbers of undirected toroidal mesh Cd1 × Cd2 for some special values of d, obtain that γd,4 (Cd1 × C3) = 2 if and only if d4(G) e1 ≤ d d4(G) for d1 ≥ 5, γd,4 (Cd1 × C4) = 2 if d4(G) (2e1-[d1+e1]/2) ≤ d d4(G) for d1 ≥ 24, and γd,4 (Cd1 × Cd2 ) = 2 if d4(G) ( e1-2) ≤ d d4(G) for d1 = d2 ≥ 14.     

Pan-H-Linked Graphs

Let H be a multigraph, possibly containing loops. An H-subdivision is any simple graph obtained by replacing the edges of H with paths of arbitrary length. Let H be an arbitrary multigraph of order k, size m, n ₀(H) isolated vertices and n ₁(H) vertices of degree one. In Gould and Whalen (Graphs Comb. 23:165–182, 2007) it was shown that if G is a simple graph of order n containing an H-subdivision H{\mathcal{H}} and d(G) 3 \fracn+m-k+n₁(H)+2n₀(H)2{\delta(G) \ge \frac{n+m-k+n_1(H)+2n_0(H)}{2}}, then G contains a spanning H-subdivision with the same ground set as H{\mathcal{H}} . As a corollary to this result, the authors were able to obtain Dirac’s famed theorem on hamiltonian graphs; namely that if G is a graph of order n ≥ 3 with d(G) 3 \fracn2{\delta(G)\ge\frac{n}{2}} , then G is hamiltonian. Bondy (J. Comb. Theory Ser. B 11:80–84, 1971) extended Dirac’s theorem by showing that if G satisfied the condition d(G) 3 \fracn2{\delta(G) \ge \frac{n}{2}} then G was either pancyclic or a complete bipartite graph. In this paper, we extend the result from Gould and Whalen (Graphs Comb. 23:165–182, 2007) in a similar manner. An H-subdivision H{\mathcal{H}} in G is 1-extendible if there exists an H-subdivision H^*{\mathcal{H}^{*}} with the same ground set as H{\mathcal{H}} and |H^*| = |H| + 1{|\mathcal{H}^{*}| = |\mathcal{H}| + 1} . If every H-subdivision in G is 1-extendible, then G is pan-H-linked. We demonstrate that if H is sufficiently dense and G is a graph of large enough order n such that d(G) 3 \fracn+m-k+n₁(H)+2n₀(H)2{\delta(G) \ge \frac{n+m-k+n_1(H)+2n_0(H)}{2}} , then G is pan-H-linked. This result is sharp.     

Upper Bounds on the Paired Domination Subdivision Number of a Graph

A paired dominating set of a graph G with no isolated vertex is a dominating set S of vertices such that the subgraph induced by S in G has a perfect matching. The paired domination number of G, denoted by γ _pr(G), is the minimum cardinality of a paired dominating set of G. The paired domination subdivision number ${{\rm sd}_{\gamma _{\rm pr}}(G)}$ is the minimum number of edges to be subdivided (each edge of G can be subdivided at most once) in order to increase the paired domination number. In this paper, we show that if G is a connected graph of order at least 4, then ${{\rm sd}_{\gamma _{\rm pr}}(G)\leq 2|V(G)|-5}$ . We also characterize trees T such that ${{\rm sd}_{\gamma _{\rm pr}}(T) \geq |V(T)| /2}$ .     

Hyponormal Toeplitz Operators on the Weighted Bergman Space

Consider j = f +[`(g)]\varphi = f + \overline {g}, where f and g are polynomials, and let T_jT_{\varphi} be the Toeplitz operators with the symbol j\varphi. It is known that if T_jT_{\varphi} is hyponormal then |f￠(z)|² 3 |g￠(z)|²|f'(z)|^{2} \geq |g'(z)|^{2} on the unit circle in the complex plane. In this paper, we show that it is also a necessary and sufficient condition under certain assumptions. Furthermore, we present some necessary conditions for the hyponormality of T_jT_{\varphi} on the weighted Bergman space, which generalize the results of I. S. Hwang and J. Lee.     

A bound on the <Emphasis Type="Italic">k</Emphasis>-domination number of a graph

Let G be a graph with vertex set V(G), and let k ⩾ 1 be an integer. A subset D ⊆ V(G) is called a k-dominating set if every vertex υ ∈ V(G)-D has at least k neighbors in D. The k-domination number γ _k (G) of G is the minimum cardinality of a k-dominating set in G. If G is a graph with minimum degree δ(G) ⩾ k + 1, then we prove that