Trees with Given Diameter Minimizing the Augmented Zagreb Index and Maximizing the ABC Index

Let G be a simple connected graph with vertex set V(G) and edge set E(G).The augmented Zagreb index of a graph G is defined asAZI(G) =∑uv∈E(G)(d_ud_v/(d_u + d_v-2))~3,and the atom-bond connectivity index(ABC index for short) of a graph G is defined asABC(G) =∑uv∈E(G)((d_u + d_v-2)/d_ud_v),where d_u and d_v denote the degree of vertices u and v in G,respectively.In this paper,trees with given diameter minimizing the augmented Zagreb index and maximizing the ABC index are determined,respectively.     

Maximizing the Minimum and Maximum Forcing Numbers of Perfect Matchings of Graphs

Let G be a simple graph with 2n vertices and a perfect matching.The forcing number f(G,M) of a perfect matching M of G is the smallest cardinality of a subset of M that is contained in no other perfect matching of G.Among all perfect matchings M of G,the minimum and maximum values of f(G,M) are called the minimum and maximum forcing numbers of G,denoted by f(G) and F(G),respectively.Then f(G)≤F(G) ≤n-1.Che and Chen(2011) proposed an open problem:how to characterize the graphs G with f(G)=n-1.Lat...     

A Note on Strong Edge Coloring of Sparse Graphs

A strong edge coloring of a graph is a proper edge coloring where the edges at distance at most 2 receive distinct colors. The strong chromatic index χ'_s(G) of a graph G is the minimum number of colors used in a strong edge coloring of G. In an ordering Q of the vertices of G, the back degree of a vertex x of G in Q is the number of vertices adjacent to x, each of which has smaller index than x in Q. Let G be a graph of maximum degree Δ and maximum average degree at most 2 k. Yang and Zhu [J. Graph Theory, 83, 334–339(2016)] presented an algorithm that produces an ordering of the edges of G in which each edge has back degree at most 4 kΔ-2 k in the square of the line graph of G, implying that χ'_s(G) ≤ 4 kΔ-2 k + 1. In this note, we improve the algorithm of Yang and Zhu by introducing a new procedure dealing with local structures. Our algorithm generates an ordering of the edges of G in which each edge has back degree at most(4 k-1)Δ-2 k in the square of the line graph of G, implying that χ'_s(G) ≤(4 k-1)Δ-2 k + 1.     

On the extra edge-connectivity of hypercubes

The classical hypercube structure is a popular topological architecture in parallel computing environments and a large number of variations based on the hypercube were posed in the past three decades. Reliability evaluation of systems is important to the design and maintenance of multiprocessor systems. The h-extra edge-connectivity of graph G(V, E) is a kind of measure for the reliability of interconnection systems, which is defined as the minimum cardinality of a subset of edge set, if any, whose deletion disconnects G and such that every remaining component has at least h vertices. This paper shows that the h-extra edge-connectivity of the hypercube Qn is a constant 2~(n-1) for2~(n-1)/3 h ≤ 2~(n-1), and n ≥ 4, which extends the result of ["Bounding the size of the subgraph induced by m vertices and extra edge-connectivity of hypercubes, Discrete Applied Mathematics, 2013, 161(16): 2753-2757"].     

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.     

EXISTENCE AND NONEXISTENCE OF SOLUTIONS FOR A HARMONIC EQUATION WITH CRITICAL NONLINEARITY

This paper is concerned with the harmonic equation(P_(?ε)) : ?u = 0, u 0 in B~n and ?u/?ν+((n-2)/2)u =((n-2)/2) Ku~(n/(n-2)?ε) on S~(n-1)where B~n is the unit ball in R~n, n ≥ 4 with Euclidean metric g_0, ?B~n= S~(n-1)is its boundary, K is a function on S~(n-1)and ε is a small positive parameter. We construct solutions of the subcritical equation(P_(-ε)) which blow up at one critical point of K. We give also a sufficient condition on the function K to ensure the nonexistence of solutions for(P_(-ε)) which blow up at one point. Finally, we prove a nonexistence result of single peaked solutions for the supercritical equation(P_(+ε)).     

Exact Solution to an Extremal Problem on Graphic Sequences with a Realization Containing Every 2-Tree on k Vertices

A simple graph G is a 2-tree if G=K_3,or G has a vertex v of degree 2,whose neighbors are adjacent,and G-v is a 2-tree.Clearly,if G is a 2-tree on n vertices,then |E(G)|=2 n-3.A non-increasing sequence π=(d_1,...,d_n) of nonnegative integers is a graphic sequence if it is realizable by a simple graph G on n vertices.[Acta Math.Sin.Engl.Ser.,25,795-802(2009)] proved that if k≥2,n≥9/2 k~2+19/2 k and π=(d_1,...,d_n) is a graphic sequence with∑_(i=1)~n di(k-2)n,then π has a realization containing every 1-tree(the usual tree) on k vertices.Moreover,the lower bound(k-2)_n is the best possible.This is a variation of a conjecture due to Erdos and Sos.In this paper,we investigate an analogue problem for 2-trees and prove that if k≥3 is an integer with k≡i(mod 3),n≥ 20[k/3] ~2+31[k/3]+12 and π=(d_1,...,d_n) is a graphic sequence with ∑_(i=1)~n d_imax{k-1)(n-1), 2 [2 k/3] n-2 n-[2 k/3] ~2+[2 k/3]+1-(-1)~i}, then π has a realization containing every 2-tree on k vertices.Moreover,the lower bound max{(k-1)(n-1), 2[2 k/3]n-2 n-[2 k/3] ~2+[2 k/3]+1-(-1)~i}is the best possible.This result implies a conjecture due to [Discrete Math.Theor.Comput.Sci.,17(3),315-326(2016)].     

Number of Induced Matchings of Graphs

A matching M of a graph G is an induced matching if no two edges in M arejoined by an edge of G.Let iz(G) denote the total number of induced matchings of G,named iz-index.It is well known that the Hosoya index of a graph is the total number of matchings and the Hosoya index of a path can be calculated by the Fibonacci sequence.In this paper,we investigate the iz-index of graphs by using the Fibonacci-Narayana sequence and characterize some types of graphs with minimum and maximum iz-index,respectively.     

通过增强型萨格勒布指数对图排序

Recently, Furtula et al. proposed a valuable predictive index in the study of the heat of formation in octanes and heptanes, the augmented Zagreb index(AZI index) of a graph G, which is defined as AZI(G) =∑uv∈E(G)( d_u d_v/d_u + d_v-2)~3,where E(G) is the edge set of G, d u and d v are the degrees of the terminal vertices u and v of edge uv, respectively. In this paper, we obtain the first five largest(resp., the first two smallest) AZI indices of connected graphs with n vertices. Moreover, we determine the trees of order n with the first three smallest AZI indices, the unicyclic graphs of order n with the minimum, the second minimum AZI indices, and the bicyclic graphs of order n with the minimum AZI index, respectively.     

BOUNDS OF EIGENVALUES OF A GRAPH

Let G be a simple graph with n vertices.We denote by λ_i(G) the i-th largest eigenvalue of G.In this paper,several results are presented concerning bounds on the eigenvalues of G.In particular,it is shown that -1≤λ_2(G)≤(n-2)/2,and the left hand equality holds if and only if G is a complete graph with at least two vertices;the right hand equality holds if and only if n is even and G?2K_(n/2).     

关于完全三部图色唯一性的一个注记

Let P(G,λ) be the chromatic polynomial of a simple graph G. A graph G is chromatically unique if for any simple graph H, P(H,λ) = P(G,λ) implies that H is isomorphic to G. Many sufficient conditions guaranteeing that some certain complete tripartite graphs are chromatically unique were obtained by many scholars. Especially, in 2003, Zou Hui-wen showed that if n 31m2 + 31k2 + 31mk+ 31m? 31k+ 32√m2 + k2 + mk, where n,k and m are non-negative integers, then the complete tripartite graph K(n - m,n,n + k) is chromatically unique (or simply χ-unique). In this paper, we prove that for any non-negative integers n,m and k, where m ≥ 2 and k ≥ 0, if n ≥ 31m2 + 31k2 + 31mk + 31m - 31k + 43, then the complete tripartite graph K(n - m,n,n + k) is χ-unique, which is an improvement on Zou Hui-wen's result in the case m ≥ 2 and k ≥ 0. Furthermore, we present a related conjecture.     

双曲空间中完备子流形的特征值估计

研究了$(n+p)$维双曲空间$\mathbb{H}^{n+p}$中完备非紧子流形的第一特征值的上界.特别地,证明了$\mathbb{H}^{n+p}$中具有平行平均曲率向量$H$和无迹第二基本形式有限$L^q(q\geq n)$范数的完备子流形的第一特征值不超过$\frac{(n-1)^2(1-|H|^2)}{4}$,和$\mathbb{H}^{n+1}(n\leq5)$中具有常平均曲率向量$H$和无迹第二基本形式有限$L^q(2(1-\sqrt{\frac{2}{n}})相似文献   

Weighted Compact Commutator of Bilinear Fourier Multiplier Operator

Let T_σ be the bilinear Fourier multiplier operator with associated multiplier σ satisfying the Sobolev regularity that sup κ∈Z∥σ_κ∥W~s(R~(2n)) ∞ for some s ∈ (n, 2n]. In this paper, it is proved that the commutator generated by T_σ and CMO(R~n) functions is a compact operator from L~(p1)(R~n, w_1) × L~(p2)(R~n, w_2) to L~p(R~n, ν_w) for appropriate indices p_1, p_2, p ∈ (1, ∞) with1 p=1/ p_1 +1/ p_2 and weights w_1, w_2 such that w = (w_1, w_2) ∈ A_(p/t)(R~(2n)).     

最大度与最小度相差不超过2的图的平衡judicious划分

图G的顶点集V(G)的一个二部划分V_1和V_2叫做平衡二部划分,如果||V_1|-|V_2||≤1成立.Bollobas和Scott猜想:每一个有m条边且最小度不小于2的图,都存在一个平衡二部划分V_1,V_2,使得max{e(V_1),e(V_2)}≤m/3,此处e(V_i)表示两顶点都在V_i(i=1,2)中的边的条数.他们证明了这个猜想对正则图(即△(G)=δ(G))成立.颜娟和许宝刚证明了每个(k,k-1)-双正则图(即△(G)-δ(G)≤1)存在一个平衡二部划分V_1,V_2,使得每一顶点集的导出子图包含大约m/4条边.这里把该结论推广到最大度和最小度相差不超过2的图G.     

一个素变量丢番图问题

设k和r是满足k≥3及r≥Ψ(k)+1的正整数,这里当3≤k≤4时,Ψ(k)=2~(k-1);而当k≥5时,Ψ(k)=1/2k(k+1).假定δ和ε是给定的足够小的正数,λ_1,λ_2,…,λ_(r+1)是不全同号且两两之比不全为有理数的非零实数.对于任意实数η与0σ2~(1-2k)/r-1,证明了:存在一个正数序列X→+∞,使得不等式|λ_1p_1~k+λ_2p_2~k+···+λ_rp_r~k+λ_(r+1)p_(r+1)+η|(max(1≤j≤r+1)p_j)~(-σ)有》■X~(■-(2~(1-2k))/(r-1)+ε组素数解(p_1,p_2,…,p_(r+1)),这里(δX)~(1/k)≤p_j≤X~(1/k)(1≤j≤r)及δX≤p_(r+1)≤X.这改进了之前的结果.     

有循环极大子群的素数幂阶群的作用是边传递的图(II)

假定Γ是一个有限的、单的、无向的且无孤立点的图,G是Aut(Γ)的一个子群.如果G在Γ的边集合上传递,则称Γ是G-边传递图.我们完全分类了当G为一个有循环的极大子群的素数幂阶群时的G-边传递图.结果为:设图Γ含有一个阶为pn(p是素数,n≥2)的自同构群,且G有一个极大子群循环,则Γ是G-边传递的,当且仅当Γ同构于下列图之一1)pmK1,pn-1-m,0≤m≤n-1;2)pmK1,pn-m,0≤m≤n;3)pmKp,pn-m-1,0≤m≤n-2;4)pn-mCpm,pm≥3,m＜n;5)2n-2K1,1;6)pn-1-mCpm,pm≥3,m≤n-1;7)2pn-mCpm,pm≥3,m≤n-1;8)2pn-mK1,pm,0≤m≤n;9)pn-mK1,2pm,0≤m≤n;10)pn-mK2,pm,0＜m≤n;11)C(2pn-m,1,pm);12)pkC(2pm-k,1,pn-m),0＜k＜m,0＜m≤n;13)(t-s,2m)C(2m 1/(t-s,2m),1,2n-1-m),其中0≤m≤n-1,2n-2(s-1)≡0(mod 2m),t≡1(mod 2),s(≠)t(mod 2m),1≤s≤2m,1≤t≤2n-1;14)∪p i=1 Ci p n-1,其中Ci p n-1=Ca1a1 [1 (i-1)pn-2]a 1 2[1 (i--1)p n-2]…a 1 (pn-1-1)[1 (i-1)p n-2]≌Cp n-1,i=1,2,…,p;15)∪2 i=1 Ci 2n-1,其中Ci 2n-1=Ca1a 1 [1 (i-1)(2n-2-1)]a1 2[1 (i-1)(2n-2-1)]…a1 (2n-1-1)[1 (i-1)(2n-2-1)]≌C2n-1,i=1,2.     

图的无符号拉普拉斯和距离无符号拉普拉斯特征值

Let G be a simple graph. We first show that ■, where δiand di denote the i-th signless Laplacian eigenvalue and the i-th degree of vertex in G, respectively.Suppose G is a simple and connected graph, then some inequalities on the distance signless Laplacian eigenvalues are obtained by deleting some vertices and some edges from G. In addition, for the distance signless Laplacian spectral radius ρQ(G), we determine the extremal graphs with the minimum ρQ(G) among the trees with given diameter, the unicyclic and bicyclic graphs with given girth, respectively.     

Two families of approximations for the gamma function

In this paper, we establish two families of approximations for the gamma function: $$ \begin{array}{lll} {\varGamma}(x+1)&=\sqrt{2\pi x}{\left({\frac{x+a}{{\mathrm{e}}}}\right)}^x {\left({\frac{x+a}{x-a}}\right)}^{-\frac{x}{2}+\frac{1}{4}} {\left({\frac{x+b}{x-b}}\right)}^{\sum\limits_{k=0}^m\frac{{\beta}_k}{x^{2k}}+O{{\left(\frac{1}{x^{2m+2}}\right)}}},\\ {\varGamma}(x+1)&=\sqrt{2\pi x}\cdot(x+a)^{\frac{x}{2}+\frac{1}{4}}(x-a)^{\frac{x}{2}-\frac{1}{4}} {\left({\frac{x-1}{x+1}}\right)}^{\frac{x^2}{2}}\\ &\quad\times {\left({\frac{x-c}{x+c}}\right)}^{\sum\limits_{k=0}^m\frac{{\gamma}_k}{x^{2k}}+O{\left({\frac{1}{x^{2m+2}}}\right)}}, \end{array}$$ where the constants ${\beta }_k$ and ${\gamma }_k$ can be determined by recurrences, and $a$ , $b$ , $c$ are parameters. Numerical comparison shows that our results are more accurate than Stieltjes, Luschny and Nemes’ formulae, which, to our knowledge, are better than other approximations in the literature.     

On the normalizing multiplier of the generalized Jackson kernel

We consider the question of evaluating the normalizing multiplier $$\gamma _{n,k} = \frac{1}{\pi }\int_{ - \pi }^\pi {\left( {\frac{{sin\tfrac{{nt}}{2}}}{{sin\tfrac{t}{2}}}} \right)^{2k} dt} $$ for the generalized Jackson kernel J _n,k (t). We obtain the explicit formula $$\gamma _{n,k} = 2\sum\limits_{p = 0}^{\left[ {k - \tfrac{k}{n}} \right]} {( - 1)\left( {\begin{array}{*{20}c} {2k} \\ p \\ \end{array} } \right)\left( {\begin{array}{*{20}c} {k(n + 1) - np - 1} \\ {k(n - 1) - np} \\ \end{array} } \right)} $$ and the representation $$\gamma _{n,k} = \sqrt {\frac{{24}}{\pi }} \cdot \frac{{(n - 1)^{2k - 1} }}{{\sqrt {2k - 1} }}\left[ {1\frac{1}{8} \cdot \frac{1}{{2k - 1}} + \omega (n,k)} \right],$$ , where $$\left| {\omega (n,k)} \right| < \frac{4}{{(2k - 1)\sqrt {ln(2k - 1)} }} + \sqrt {12\pi } \cdot \frac{{k^{\tfrac{3}{2}} }}{{n - 1}}\left( {1 + \frac{1}{{n - 1}}} \right)^{2k - 2} .$$ .