图和线图的谱性质

Let G be a simple connected graph with n vertices and m edges,Lo be the line graph of G and λ1(LG)≥λ2 (LG)≥...≥λm(LG) be the eigenvalues of the graph LG,.. In this paper, the range of eigenvalues of a line graph is considered. Some sharp upper bounds and sharp lower bounds of the eigenvalues of Lc. are obtained. In oarticular,it is oroved that-2cos(π/n)≤λn-1(LG)≤n-4 and λn(LG)=-2 if and only if G is bipartite.     

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

二树的ABC指标

The atom-bond connectivity(ABC) index of a graph G, introduced by Estrada,Torres, Rodr′?guez and Gutman in 1998, is defined as the sum of the weights(1/di+1/dj-2/didj )~(1/2) of all edges vivj of G, where di denotes the degree of the vertex vi in G. In this paper, we give an upper bound of the ABC index of a two-tree G with n vertices, that is, ABC(G) ≤(2n- 4)2~(1/2)/2+(2n-4)~(1/2)/n-1. We also determine the two-trees with the maximum and the second maximum ABC index.     

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"].     

On strong metric dimension of graphs and their complements

A vertex x in a graph G strongly resolves a pair of vertices v, w if there exists a shortest x-w path containing v or a shortest x-v path containing w in G. A set of vertices S■V(G) is a strong resolving set of G if every pair of distinct vertices of G is strongly resolved by some vertex in S. The strong metric dimension of G, denoted by sdim(G), is the minimum cardinality over all strong resolving sets of G. For a connected graph G of order n≥2, we characterize G such that sdim(G) equals 1, n-1, or n-2, respectively. We give a Nordhaus-Gaddum-type result for the strong metric dimension of a graph and its complement: for a graph G and its complement G, each of order n≥4 and connected, we show that 2≤sdim(G)+sdim(G)≤2( n-2). It is readily seen that sdim(G)+sdim(G)=2 if and only if n=4; we show that, when G is a tree or a unicyclic graph, sdim(G)+sdim(G)=2(n 2) if and only if n=5 and G ～=G ～=C5, the cycle on five vertices. For connected graphs G and G of order n≥5, we show that 3≤sdim(G)+sdim(G)≤2(n-3) if G is a tree; we also show that 4≤sdim(G)+sdim(G)≤2(n-3) if G is a unicyclic graph of order n≥6. Furthermore, we characterize graphs G satisfying sdim(G)+sdim(G)=2(n-3) when G is a tree or a unicyclic graph.     

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

Graphs with vertex rainbow connection number two

An edge colored graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of a graph G, denoted by rc(G), is the smallest number of colors that are needed in order to make G rainbow connected. A vertex colored graph G is vertex rainbow connected if any two vertices are connected by a path whose internal vertices have distinct colors. The vertex rainbow connection number of G, denoted by rvc(G), is the smallest number of colors that are needed in order to make G vertex rainbow connected. In 2011, Kemnitz and Schiermeyer considered graphs with rc(G) = 2.We investigate graphs with rvc(G) = 2. First, we prove that rvc(G) 2 if |E(G)|≥n-22 + 2, and the bound is sharp. Denote by s(n, 2) the minimum number such that, for each graph G of order n, we have rvc(G) 2provided |E(G)|≥s(n, 2). It is proved that s(n, 2) = n-22 + 2. Next, we characterize the vertex rainbow connection numbers of graphs G with |V(G)| = n, diam(G)≥3 and clique number ω(G) = n- s for 1≤s≤4.     

一类有限p-群的因子分解数（英文）

Let p be a prime number and f_2(G) be the number of factorizations G = AB of the group G, where A, B are subgroups of G. Let G be a class of finite p-groups as follows,G = a, b | a~(p~n)= b~(p~m)= 1, a~b= a~(p~(n-1)+1), where n m ≥ 1. In this article, the factorization number f_2(G) of G is computed, improving the results of Saeedi and Farrokhi in [5].     

Erds-Ko-Rado Theorem for Ladder Graphs

For a graph G and an integer r≥1,G is r-EKR if no intersecting family of independent r-sets of G is larger than the largest star(a family of independent r-sets containing some fixed vertex in G),and G is strictly r-EKR if every extremal intersecting family of independent r-sets is a star.Recently,Hurlbert and Kamat gave a preliminary result about EKR property of ladder graphs.They showed that a ladder graph with n rungs is 3-EKR for all n≥3.The present paper proves that this graph is r-EKR for all 1≤r≤n,and strictly r-EKR except for r=n-1.     

The automorphism group of a generalized extraspecial p-group

In this paper, the automorphism group of a generalized extraspecial p-group G is determined, where p is a prime number. Assume that |G| = p 2n+m and |ζG| = p m , where n 1 and m 2. (1) When p is odd, let Aut G G = {α∈ AutG | α acts trivially on G }. Then Aut G G⊿AutG and AutG/Aut G G≌Z p-1 . Furthermore, (i) If G is of exponent p m , then Aut G G/InnG≌Sp(2n, p) × Z p m-1 . (ii) If G is of exponent p m+1 , then Aut G G/InnG≌ (K Sp(2n-2, p))×Z p m-1 , where K is an extraspecial p-group of order p 2n-1 . In particular, Aut G G/InnG≌ Z p × Z p m-1 when n = 1. (2) When p = 2, then, (i) If G is of exponent 2 m , then AutG≌ Sp(2n, 2) × Z 2 × Z 2 m-2 . In particular, when n = 1, |AutG| = 3 · 2 m+2 . None of the Sylow subgroups of AutG is normal, and each of the Sylow 2-subgroups of AutG is isomorphic to H K, where H = Z 2 × Z 2 × Z 2 × Z 2 m-2 , K = Z 2 . (ii) If G is of exponent 2 m+1 , then AutG≌ (I Sp(2n-2, 2)) × Z 2 × Z 2 m-2 , where I is an elementary abelian 2-group of order 2 2n-1 . In particular, when n = 1, |AutG| = 2 m+2 and AutG≌ H K, where H = Z 2 × Z 2 × Z 2 m-1 , K = Z 2 .     

$A_n-$型有限维代数的整体维数

设$k$是一个代数闭域, $n$是一个自然数,本文给出了一个精确刻画$A_{n}$-型有限维$k$-代数的整体维数的技巧.据此给出了$A_{n}$-型有限维$k$-代数的所有可能的整体维数.特别的,如果$n>1$,我们指出其中最大的是 $n-1$,最小的是 $1$.     

DIAGNOSABILITY OF CAYLEY GRAPH NETWORKS GENERATED BY TRANSPOSITION TREES UNDER THE COMPARISON DIAGNOSIS MODEL

Diagnosability of a multiprocessor system is one important study topic.Cayley graph network Cay(T_n,S_n) generated by transposition trees Tnis one of the attractive underlying topologies for the multiprocessor system.In this paper,it is proved that diagnosability of Cay(T_n,S_n) is n-1 under the comparison diagnosis model for n ≥ 4.     

剩余为几乎2-正则的6-圈系

Let Kn be a complete graph on n vertices. In this paper, we find the necessary conditions for the existence of a 6-cycle system of Kn - L for every nearly 2-regular leave L of Kn. This condition is also sufficient when the number of vertices of L is n - 4.     

The Monge-Ampère Equation for Strictly $(n−1)$-Convex Functions with Neumann Condition

A $C^2$ function on $\mathbb{R}^n$ is called strictly $(n-1)$-convex if the sum of any $n-1$ eigenvalues of its Hessian is positive. In this paper, we establish a global $C^2$ estimates to the Monge-Ampère equation for strictly $(n-1)$-convex functions with Neumann condition. By the method of continuity, we prove an existence theorem for strictly $(n-1)$-convex solutions of the Neumann problems.     

零度为$n-7$的双圈符号图

Let Γ be a signed graph and A(Γ) be the adjacency matrix of Γ. The nullity ofΓ is the multiplicity of eigenvalue zero in the spectrum of A(Γ). In this paper, the connected bicyclic signed graphs(including simple bicyclic graphs) of order n with nullity n-7 are completely characterized.     

No Helly Theorem for Stabbing Translates by Lines in R<Superscript>3</Superscript>

For each $n>2$ we construct a convex body $K\subset {\Bbb R}^3$ and a finite family ${\cal F}$ of disjoint translates of $K$ such that any $n-1$ members ${\cal F}$ admit a line transversal, but ${\cal F}$ has no line transversal.     

拟树图按第二大无符号拉普拉斯特征值排序

A connected graph G=(V,E) is called a quasi-tree graph if there exists a vertex v_0∈V(G) such that G-v_0 is a tree.In this paper,we determine all quasi-tree graphs of order n with the second largest signless Laplacian eigenvalue greater than or equal to n-3.As an application,we determine all quasi-tree graphs of order n with the sum of the two largest signless Laplacian eigenvalues greater than to 2 n-5/4.     

An Extension of the Win Theorem: Counting the Number of Maximum Independent Sets

Win proved a well-known result that the graph G of connectivity κ(G) withα(G) ≤κ(G) + k-1(k ≥ 2) has a spanning k-ended tree, i.e., a spanning tree with at most k leaves. In this paper, the authors extended the Win theorem in case when κ(G) = 1 to the following: Let G be a simple connected graph of order large enough such that α(G) ≤ k + 1(k ≥ 3) and such that the number of maximum independent sets of cardinality k + 1 is at most n-2k-2. Then G has a spanning k-ended tree.     

混合图的Hermitian邻接矩阵的零维数

A mixed graph means a graph containing both oriented edges and undirected edges. The nullity of the Hermitian-adjacency matrix of a mixed graph G, denoted by ηH(G),is referred to as the multiplicity of the eigenvalue zero. In this paper, for a mixed unicyclic graph G with given order and matching number, we give a formula on ηH(G), which combines the cases of undirected and oriented unicyclic graphs and also corrects an error in Theorem 4.2 of [Xueliang LI, Guihai YU. The skew-rank of oriented graphs. Sci. Sin. Math., 2015, 45:93-104(in Chinese)]. In addition, we characterize all the n-vertex mixed graphs with nullity n-3, which are determined by the spectrum of their Hermitian-adjacency matrices.     

On classification of polarized varieties with non-integral nef values

Let be an -dimensional normal projective variety with only Gorenstein, terminal, -factorial singularities. Let be an ample line bundle on . Let denote the nef value of . The classification of via the nef value morphism is given for the situations when satisfies or .