ON THE LEAST EIGENVALUE OF A GRAPH

Let G be a simple graph with n vertices and λ_n(G) be the least eigenvalue of G.In this paper, we show that, if G is connected but not complete, then λ_n(G)≤λ_n(K_(n-1)~1)and the equality holds if and only if G K_(n-1)~1, where K_(n-1)~1, is the graph obtained by thecoalescence of a complete graph K_(n-1) of n-1 vertices with a path P_2 of length one of itsvertices.     

FORBIDDEN SUBGRAPHS,DEGREES,NEIGHBORHOOD UNIONS AND CIRCUMFERENCES OF GRAPHS

Combining forbidden subgraphs with degree restrictions and neighborhood unionrestrictions,respectively,we prove the following results:(1) Let G be a 2-connected graph of order n,and 3≤c≤n.If for each induced subgraphL of order four of G(?)|V_1(L)∩S_c|≥2 if L≌K_(1,3),and |V(L)∩S_c|≥1 if L≌P_4,then thecircumference of G is at least c,where V_1(L)is the set of vertices with degree 1 of L,S_c isthe set of vertices with degree at least c/2 of G and P_4 is a path of order 4.(2) Let G be a 2-connected graph of order n,and n≥s+2.If for each induced subgraphL of G isomorphic to K_(1,3)or P_4,d_L(u,v)=2(?)|N(u)∪N(v)|≥s,then the circumferencec (G) of G is at least s+2.Moreover,if n≥s+3 and s is odd,then c(G)≥s+3.     

On the Gracefulness of the Digraphs n·Cm＊

A digraph D（V, E） is said to be graceful if there exists an injection f ： V（G） →{0, 1,... , ｜E｜} such that the induced function f＇ ： E（G） --~ {1, 2,… , ｜E｜} which is defined by f＇ （u, v） = [f（v） - f（u）] （rood ｜E｜＋ 1） for every directed edge （u, v） is a bijection. Here, f is called a graceful labeling （graceful numbering） of D（V, E）, while f＇ is called the induced edge＇s graceful labeling of D. In this paper we discuss the gracefulness of the digraph n- Cm and prove that n. Cm is a graceful digraph for m = 15, 17 and even     

EDGE CONDITION FOR A HAMILTONIAN BIPARTITE GRAPH TO BE BIPANCYCLIC

Let G be a hamiltonian, bipartite graph on 2n vertices, where n>3. It isshown that if e(G)>n(n-1)/2 + 2 then G contains cycles of every possible even length.This improves a result of Entringer and Schmeichel.     

SOME THEOREMS OF THE NORDHAUS-GADDUM CLASS

Let the chromatic number of G, the edge chromatic number of G and thetotal chromatic number of G be denoted by x(G), x_1(G) and x_2(G), respectively. Forany simple graph G of order p and its complement G, the following inequalities of theNordhaus-Gaddum class are obtained:(i)|2p~(1/2)|-ε_1≤x(G)+x_1(G)≤2p-2 and 0≤x(G)·x_1(G)≤(p-1)~2 for p≥2,(ii)|2p~(1/2)|+ε_1≤x(G)+x_2(G)≤2p-1 and 0≤x(G)·x_2(G)≤p(p-1) for p≥3,(iii)p≤x_1(G)+x_2(G)≤2p-1 and 0≤x_1(G)·x_2(G)≤p(p-1) for p≥3,where ε_1=0, if p~(1/2) is an odd integer, 1, otherwise,ε_2=1, if p~(1/2) is an even integer, 0, otherwise,and [x] denotes the ceiling of x. We also show that these bounds are sharp for everypositive integer p.     

DEGREE CONDITIONS FOR GRAPHS TO BE FRACTIONAL （a, b, n）-CRITICAL GRAPHS

Let G be a graph, and a and b be integers with a ≤ b. A graph G is called a fraetional （a, b, n）-critical graph if after any n vertices of G are deleted the remaining subgraph has a fractional [a, b]-factor. In this paper two degree conditions for graphs to be fractional （a, b, n）-eritical graphs are presented, and the degree conditions are sharp in some sense.     

A FURTHER GENERALIZATION OF JUNG''''S THEOREM

Let G be a graph of order n. We define the distance between two vertices u andv in G, denoted by d(u, v), as the minimum value of the lengths of all u-v paths. We writeσ_k(G)=min{∑_i=1~k d(v_i)|{v_1, v_2,…, v_k} is an independent set in G} and NC2(G)=min {|N(u)∪N(v)| | d(u, v)=2}. We denote by ω(G) the number of components of agraph G. A graph G is called 1-tough if ω(G\S)≤|S| for every subset S of V(G) withω(G\S)>l. By c(G) we denote the length of the longest cycle in G; in particular, G iscalled a Hamiltonian graph if c(G)=n. H.A. Jung proved that every 1-tough graphwith order n≥11 and σ2≥n-4 is Hamiltonian. We generalize it further as follows: ifG is a 1-tough graph and σ3(G)≥n, then c(G)≥min {n,2NC2(G)+4}. Thus, theconjecture of D. Bauer, G. Fan and H.J. Veldman in [2] is completely solved.     

STRONG EMBEDDING OF HP-GRAPHS ON SURFACE WITH HIGHER GENUS

In 1990, Bondy posed the small circuit double cover （SCDC） conjecture： Every 2-connected graph has a circuit double cover （CDC） with the number of circuits less than ｜v｜ （the order of the vertex set V）. The strong embedding conjecture states that every 2-connected graph has a strong embedding on some surface in which the boundary of each face is a circuit. In this paper, HP-graph is defined as the graph which has a strong embedding on the projective plane with one face of valence ｜V｜ and the other faces of valence 3. And it is proved that the HP-graph has a strong embedding with ｜V｜ - 1 or less faces on some surface, which confirms both the SCDC conjecture and the strong embedding conjecture.     

PACKING A TREE OF ORDER p WITH A （p,p＋1）—GRAPH

Let G1 and G2 be two graphs of the same order,If G1 is isomorphic to a spanning subgraph of the complement of G2,then we say that G1 and G2 are packable.A graph G is called a (p,m)-graph if G has p vertices and m edges.The main purpose of this paper is to present a necessary and sufficient condition for a tree of order p and a (p,p 1)-graph to be packable.     

SOME PROPERTIES ON PATHS IN MATROID BASE GRAPHS

Let G be the base graph with n vertices of any matroid.It is proved that for anytwo vertices of G there are at least r internally disjoint shortest paths joining them where r istheir distance.Furthermore,for any integer k,r≤k≤n-1,there is a path of length k or k+1in G joining them.If M is a simple matroid and P=bb_1…b_(r-1)b′is a shortest path in the basegraph G of M,then for any integer k,r≤k≤n-1,there is a path of length k between b andb′containing b_1,…,b_(r-1).Therefore the results in [5] are generalized.     

A NOTE ON THE PAPER“A NEW SUFFICIENT CONDITION FOR HAMILTONIAN GRAPHS”

We prove that if G is a graph of order n and connectivity k,and thereexists some t,t(?)k,such that for every independent set S={x_0,x_1,…x_t} ofcardinality t+1,we havesum from i=0 to t |N(S/{x_i}|>t(n-1),then G is Hamiltonian.     

On the Toughness and Fractional Perfect Matching of Graphs

In this paper, we prove the following results： let G be a graph with even order P ≥ 2k ＋ 2, if t（G） 〉 k, then the subgraph of G obtained by deleting any 2k-edges or 2k-vertices has a fractional perfect matching.     

IMPLICIT DEGREES AND CHVATAL'S CONDITION FOR HAMILTONICITY

Based on the ideas in[9],an integer d~0(v),called the implicit degree of v whichsatisfies d~0(v)≥d(v),is associated with each vertex v of a graph G.It is proved that if theimplicit degree sequence d_1~0,d_2~0,…,d_n~0(where d_1~0≤d_2~0≤…≤d_n~0)of a simple graph G on n≥3vertices satisfiesd_i~0≤i相似文献   

BIPANCYCLISM IN HAMILTONIAN BIPARTITE GRAPHS

It is shown that if G is a hamiltonian bipartite graph on 2n vertices and δ(G)>2n/5 2,where n≥60,then G is bipancyclic.     

ON CLASSIFICATION OF HIGHER ORDER IMMERSIONS OF MANIFOLDS

Denote by V_f~p the set of homotopy classes of codimensiom m framings of the p thorder stable normal bundle of a map f:M~n→N~(v(n,p)+m).Where 3≤m=n-1 or m=n-2 butn=0,1 mod 4.We determine in this paper the set V_f~p and then the set of p-homotopyclasses of p-immersions homotopic to f for some special cases.     

CYCLES CONTAINING MANY VERTICES OF SUBSETS IN GRAPHS WITH LARGE DEGREE SUMS AND NEIGHBORHOOD UNIONS

1. ResultsWe use[IJ for terminology and notations not defined here and consider simple graph only.Let G be a graph of order n and X C V(G). A graph G is called 1--tough if w(G\S) 5 ISIfor any S g V(G) with w(G\S) > 1, where w(G\S) denotes the number of components ofgraph G\S. A cycle C of G is called X-longest if no cycle of G contains more venices of Xthan C, and by c(X) we denote the number of venices of X in an X-longest cycle. A cycle Cof G is called X-dominating if all neigh…     

A SIMPLIFIED APPROACH TO EMBEDDING PROBLEMS IN NORMAL BORDISM FRAMEWORK

The purpose of this paper is to simplify the computations of the nor-mal bordism groups Ω_i(W_f,M×P~∞;(?))and Ω_i(C_f,(?)w;θ_f)which Salomonsenand Dax introduced respectively to study the existence and isotopy classificationof differential embeddings of manifolds in manifolds in the metastable range.Asimpler space pair(K_f,M×P~∞)is constructed to replace(W_f,M×P~∞).It isshown that(K_f,M×P~∞)is homotopy equivalent to(W_f,M×P~∞)and homotopy(n-1)-equivalent to(C_f,(?)W).To demonstrate the efficacy of this simplification,the isotopy groups [M~n(?)RP~(n+k)],if n(?)2k-4 and M~n is a closed(n-k+2)-connected manifold,and[M~n(?)L(p;q_1…,q_m)],if 3n(?)4m-2,M~n is a closed(2n-2m+1)-connected manifold and L is a (2m+1)-dimensional lens space,arespecifically computed.     

EXISTENCE OF HAMILTONIAN k-FACTOR

A Hamiltonian k-factor is a k-factor containing a Hamiltonian cycle. An n/2-critical graph G is a simple graph of order n which satisfies S(G) > n/2 and δ(G - e)< n/2 for any edge e ∈ E(G). Let k > 2 be an integer and G be an n/2-critical graph of even order n > 8k-14. It is shown in this paper that for any given Hamiltonian cycle C except that G - C consists of two components of odd orders when fc is odd, G has a k-factor containing C.     

Asymptotic Normality of Maximum Quasi-Likelihood Estimators in Generalized Linear Models with Fixed Design*

In generalized linear models with fixed design, under the assumption λ↑_n→∞ and other regularity conditions, the asymptotic normality of maximum quasi-likelihood estimator ^↑βn, which is the root of the quasi-likelihood equation with natural link function ∑i=1^n Xi（yi -μ（Xi′β）） = 0, is obtained, where λ↑_n denotes the minimum eigenvalue of ∑i=1^nXiXi′, Xi are bounded p × q regressors, and yi are q × 1 responses.     

An Upper Bound for the Cubicity of Folded Hypercube

For a graph, its boxicity is the minimum dimension k such that G is representable as the intersection graph of axis-parallel boxes＇in the k-dimension space. When the boxes are restricted to be axis-parallel k-dimension cube＇s, the minimum k required to represent G is called the cubicity of G. In this paper, a special graph .called unit-interval graph. IG[X, Y] is given, then 2n such graphs which have the same vertices as V（FQn） are constructed, where FQ, is the n-dimension folded hypercube. Thanks to the specia] structure of IG[X, Y], the result that cubicity（FQn）≤ 2n is proved.