A mixed graph G^(-) is obtained by orienting some edges of G, where G is the underlying graph of G^(-) . The positive inertia index, denoted by p~+( G), and the negative inertia index, denoted by n~-(G^(-) ), of a mix...A mixed graph G^(-) is obtained by orienting some edges of G, where G is the underlying graph of G^(-) . The positive inertia index, denoted by p~+( G), and the negative inertia index, denoted by n~-(G^(-) ), of a mixed graph G^(-) are the integers specifying the numbers of positive and negative eigenvalues of the Hermitian adjacent matrix of G^(-) , respectively. In this paper, the positive and negative inertia indices of the mixed unicyclic graphs are studied. Moreover, the upper and lower bounds of the positive and negative inertia indices of the mixed graphs are investigated, and the mixed graphs which attain the upper and lower bounds are characterized respectively.展开更多
Let a, b, r be nonnegative integers with 1 ≤ a ≤ b and r ≥ 2. Let G be a graph of order n with n 〉(a+2 b)(r(a+b)-2)/b.In this paper, we prove that G is fractional ID-[a, b]-factor-critical if δ(G)≥bn/a...Let a, b, r be nonnegative integers with 1 ≤ a ≤ b and r ≥ 2. Let G be a graph of order n with n 〉(a+2 b)(r(a+b)-2)/b.In this paper, we prove that G is fractional ID-[a, b]-factor-critical if δ(G)≥bn/a+2 b+a(r-1)and |NG(x1) ∪ NG(x2) ∪…∪ NG(xr)| ≥(a+b)n/(a+2 b) for any independent subset {x1,x2,…,xr} in G. It is a generalization of Zhou et al.'s previous result [Discussiones Mathematicae Graph Theory, 36: 409-418(2016)]in which r = 2 is discussed. Furthermore, we show that this result is best possible in some sense.展开更多
In this paper, we determine the neighbor connectivity κNB of two kinds of Cayley graphs: alter- nating group networks ANn and star graphs Sn; and give the exact values of edge neighbor connectivity λNB of ANn and C...In this paper, we determine the neighbor connectivity κNB of two kinds of Cayley graphs: alter- nating group networks ANn and star graphs Sn; and give the exact values of edge neighbor connectivity λNB of ANn and Cayley graphs generated by transposition trees Fn. Those are κNB(ANn) = n-1, λNB(ANn) = n-2 and κNB(Sn) = λNB(Гn) = n - 1.展开更多
An embedding of a digraph in an orientable surface is an embedding as the underlying graph and arcs in each region force a directed cycle. The directed genus is the minimum genus of surfaces in which the digraph can b...An embedding of a digraph in an orientable surface is an embedding as the underlying graph and arcs in each region force a directed cycle. The directed genus is the minimum genus of surfaces in which the digraph can be directed embedded. Bonnington, Conder, Morton and McKenna [J. Cornbin. Theory Ser. B,85(2002) 1-20] gave the problem that which tournaments on n vertices have the directed genus [(n-3)(n-4)/12]the genus of Kn. In this paper, we use the current graph method to show that there exists a tournament, whichhas the directed genus[(n-3)(n-4)/12], on n vertices if and only if n = 3 or 7 (mod 12).展开更多
基金the National Natural Science Foundation of China (Nos. 11971054 and 12161141005)the Fundamental Research Funds for the Central Universities (No. 2016JBM071)。
文摘A mixed graph G^(-) is obtained by orienting some edges of G, where G is the underlying graph of G^(-) . The positive inertia index, denoted by p~+( G), and the negative inertia index, denoted by n~-(G^(-) ), of a mixed graph G^(-) are the integers specifying the numbers of positive and negative eigenvalues of the Hermitian adjacent matrix of G^(-) , respectively. In this paper, the positive and negative inertia indices of the mixed unicyclic graphs are studied. Moreover, the upper and lower bounds of the positive and negative inertia indices of the mixed graphs are investigated, and the mixed graphs which attain the upper and lower bounds are characterized respectively.
基金supported by the National Natural Science Foundation of China(Nos.11371052,11731002)the Fundamental Research Funds for the Central Universities(Nos.2016JBM071,2016JBZ012)the 111 Project of China(B16002)
文摘Let a, b, r be nonnegative integers with 1 ≤ a ≤ b and r ≥ 2. Let G be a graph of order n with n 〉(a+2 b)(r(a+b)-2)/b.In this paper, we prove that G is fractional ID-[a, b]-factor-critical if δ(G)≥bn/a+2 b+a(r-1)and |NG(x1) ∪ NG(x2) ∪…∪ NG(xr)| ≥(a+b)n/(a+2 b) for any independent subset {x1,x2,…,xr} in G. It is a generalization of Zhou et al.'s previous result [Discussiones Mathematicae Graph Theory, 36: 409-418(2016)]in which r = 2 is discussed. Furthermore, we show that this result is best possible in some sense.
基金Supported by the National Natural Science Foundation of China(No.11371052,11731002,11571035)
文摘In this paper, we determine the neighbor connectivity κNB of two kinds of Cayley graphs: alter- nating group networks ANn and star graphs Sn; and give the exact values of edge neighbor connectivity λNB of ANn and Cayley graphs generated by transposition trees Fn. Those are κNB(ANn) = n-1, λNB(ANn) = n-2 and κNB(Sn) = λNB(Гn) = n - 1.
基金Supported by the National Natural Science Foundation of China(No.11731002)the Fundamental Research Funds for the Central Universities(Nos.2016JBM071,2016JBZ012)
文摘An embedding of a digraph in an orientable surface is an embedding as the underlying graph and arcs in each region force a directed cycle. The directed genus is the minimum genus of surfaces in which the digraph can be directed embedded. Bonnington, Conder, Morton and McKenna [J. Cornbin. Theory Ser. B,85(2002) 1-20] gave the problem that which tournaments on n vertices have the directed genus [(n-3)(n-4)/12]the genus of Kn. In this paper, we use the current graph method to show that there exists a tournament, whichhas the directed genus[(n-3)(n-4)/12], on n vertices if and only if n = 3 or 7 (mod 12).