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.     

On the Star Chromatic Number of Graph Products

1　 IntroductionThroughout this paper,we only consider simple graphs.Letkanddbe natural numberssuch thatk 2 d.A ( k,d) -coloring of a graph G=( V,E) is a map c:V|→ Zk,such thatforeach edge( u,v)∈ E,|c( u) -c( v) |k d,where|x|k=min{|x|,k-|x|},and Zk={0 ,1 ,2 ,… ,k-1 }.Itis obvious thata( k,1 ) -coloring ofa graph is justan ordinaryk-coloringof G.The star-chromatic numberχ* ( G) of a graph G is defined by:χ* ( G) =inf{k/ d∶ G has a ( k,d) -coloring}.　　It is proved in[1 ,2 ] that th…     

ON CONNECTIVITIES OF BASE GRAPHS OF SOME MATROIDS

If a matroid M without loops has basic corank γ_1 and 2-corank γ_2,and G is a base graphof M,then k(G)≥2r_1+r_2 where k(G)denotes the connectivity of G.     

EQUITABLE COLORINGS OF LINE GRAPHS AND COMPLETE r-PARTITE GRAPHS

1. IntroductionLet G be a graph with vertex set V(G), edge set E(G), maximum degree A(G), minimumdegree 8(G), vertex chromatic number X(G), and edge chromatic number X'(G). G is equitablyk-colorable if V(G) can be pajrtitioned icao k independent sets VI, V2,'', Vk such that llKI III 1 5 1 for all i and j. The such smallest integer k as above is called the equitable chromaticnumber of G, denoted by X= (G). Similaxly we can define the equitable edge chromatic numberof a graph G and d…     

VERTEX-DISJOINT QUADRILATERALS IN BIPARTITE GRAPHS

H. Wang considered the minimum degrees condition that G has large vertex-disjoint cycles in bipartite graphs. Motivated by this, we consider the small vertex-disjoint cycles in bipartite graphs in this paper. We prove the following result: Let m > 3, n > 2 and k >1 be three integers. Let G = (V1,V2;E) be a bipartite graph with | V1| = | V2| =n > 2k 1. If the minimum degreefor any cycle C of G with length 2m, then G contains k vertex-disjoint cycles of length 4. Moreover, the degrees condition is sharp.     

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.     

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.     

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.     

ON NICE SEQUENCES CONCERNING HAMILTONICITY OF GRAPHS

In the paper, the (k-1)-traceable-nice ((k-1)-T-nice) and k-homogeneously-traceable-nice (k-HT-nice) sequence are defined similarly to the definition of k-Hamilton-nice (k-H-nice) and (k+1)-Hamilton-connected-nice ((k+1)-HC-nice) sequence. Therelationships among these four nice sequences are discussed. The main results are asfollows: Let_η=(a_1, a_2,…, a_(k+1) be a non-negative rational sequence, k≥2. (1) If η is(k+1)-HC-nice and a_(k+1)=2, then η is k-HT-nice, (2) If η is k-HT-nice and a_(k+1)=2,then η is (k-1)-T-nice, (3) If η is k-H-nice, then η is k-HT-nice. Meanwhile, four unsolvedproblems on these topics are proposed.     

GRAPHS WHOSE CIRCULAR CLIQUE NUMBER EQUAL THE CLIQUE NUMBER

The circular clique number of a graph G is the maximum fractional k/d such that G^kd admits a homomorphism to G. In this paper, we give some sufficient conditions for graphs whose circular clique number equal the clique number, we also characterize the K1,3-free graphs and planar graphs with the desired property.     

A Degree Condition on Long Paths and Large Cycles

We present a new condition ensuring the existence of a large cycle of passing throughgiven edge.Let l(C)denote the length of the cycle C.Suppose G is a 4-connected graph withvertices set{x_1,x_2….x_n}and edge set E and with the property that,for any two positiveintegers j and k,j相似文献   

(4m, m)-CHOOSABILITY OF PLANE GRAPHS

1 IntroductionAll graphs considered in tabs paper are abate and sable. Undecked notations and termalnologies can be found in [if.Let G = (V, E,F) be a plase graph, where V, E and F denote the s6t of venices, edgesand faces of G, respectively. We use NG(v) and dG(v) to denote the set and nUmber of venicesadjacent to a vertex yi respectively, and use 6(G) to denote the inininuun degree of G. A vertexv is called a k-vertex if v has degree k. A face of a plane graph is said to be incident w…     

A NEW SUFFICIENT CONDITION FOR S-CIRCUITS IN GRAPHS

In[1],P.Paulraja posed the following problem:Let G be a 2-connected graph suchthat δ(G)≥3,where δ(G)denotes the minimum degree of G.If each edge of G lies on either a cycle oflength 3 or a cycle of length 4,is it true that G has a spanning Eulerian subgraph?A related case inwhich δ(G)≥4 is settled affairmatively in this paper.     

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.     

A GENERALIZATION OF THE n-QUEEN PROBLEM

A generalization of the well-known n-queen problem is to put N×k‘queens’on an k×nchessboard in such a way that each row and each column contains exactly k‘queens’and eachdiagonal with length from 1 to n and slope either 1 or -1 contains at most k‘queens’.Aconstruction is given to show that this is always possible whenever n≥4 and n≥k≥1.     

GLOBAL CONVERGENCE OF THE DAI-YUAN CONJUGATE GRADIENT METHOD WITH PERTURBATIONS

In this paper, the authors propose a class of Dai-Yuan （abbr. DY） conjugate gradient methods with linesearch in the presence of perturbations on general function and uniformly convex function respectively. Their iterate formula is xk＋1 = xk ＋ αk（sk ＋ ωk）, where the main direction sk is obtained by DY conjugate gradient method, ωk is perturbation term, and stepsize αk is determined by linesearch which does not tend to zero in the limit necessarily. The authors prove the global convergence of these methods under mild conditions. Preliminary computational experience is also reported.     

Global Convergence of the Conjugate Descent Method Under a kind of Inexact Line Search Conditions

1　 IntroductionWe consider the unconstrained optimizatoin problem( P) :minf( x) ,x∈ Rnwhere f:Rn→R is continuously differentiable and its gradient f( x) is denoted by g( x) .The conjugate gradient method is useful for calculating local unconstrained optimizationproblem of differentiable functions of many variables,it has the following form:xk 1 =xk λkdk ( 1 .1 )dk=-gk,k =1-gk βkdk- 1 ,k 2 ( 1 .2 )whereλk is a step-size obtained by a line search,andβk is a parameter,which can beobtaine…     

THE NORMALITY OF CAYLEY GRAPHS OF FINITE ABELIAN GROUPS WITH VALENCY 5

1. IntroductionLet G be a finite group and S a subset of G not colltaining the idelltity elemellt 1. TheCayley digraph X ~ Cay(G, S) of G on S is defined byV(X) = G, E(X) ~ {(g, sg)jg E G, s E S}.Immediately from the definition there are three obvious facts: (1) Ant(X), the automorphismgroup of X, contains the right regular representation GR of G; (2) X is connected if and onlyif G = (S}, (3) X is an undirected graph (by coalescing each pair (g, sg) and (sg, g) of directededges int…     

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.     

MINIMALLY （n, λ）-CONNECTED GRAPHS OF LOW ORDER AND MAXIMAL SIZE＊

A. Kaneko and K. Ota proved that for a minimally （n, λ）-connected graph G, if ｜G｜ = p ≥ 3n - 1, then e（G） ≤ nλ（｜G｜ - n）; and if e（G） = nλ（｜G｜ - n）, then G is isomorphic to the graph Kn^λ,p-n which is obtained from the complete bipartite graph Kn,p-n by replacing each edge with A multiple edges; if 3n - 1 ≥ ｜G}≥ n ＋ 1, then e（G） ≤λ（｜G｜ ＋ n）^2/8. In this paper, we determine all the minimally （n, λ）-connected graphs with order p and the maximum size λ（p＋n）^2/8 for 3n- 1 ≥ p ≥ n＋ 1 for 3n-1≥p≥n＋1.