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…     

SPANNING TRAILS OF GRAPHS

Let G be a 2-edge-connected simple graph.We give a sufficient condition in which for anyx,y∈V(G),there is an(x,y)-trail which contains every vertex of G(x-y is allowed)exceptsome graphs.     

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.     

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.     

MINIMUM FILL-IN PROBLEM OF GRAPHS

ＭＩＮＩＭＵＭＦＩＬＬ－ＩＮＰＲＯＢＬＥＭＯＦＧＲＡＰＨＳＹＵＡＮＪｉｎｊｉａｎｇ（ＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ，ＺｈｅｎｇｚｈｏｕＵｎｉｖｅｒｓｉｔｙ，Ｚｈｅｎｇｚｈｏｕ４５００５２，Ｃｈｉｎａ）ＺＨＡＮＧＨｅｐｉｎｇ（Ｄｅｐａｒ...     

LONG DOMINATING CYCLES IN GRAPHS

1.IntroductionAllgraphsconsideredinthispaperwillbefiniteandsimple.WeuseBondyandMurty[1]forterminologyandnotationsnotdefinedhere.LetG=(V,E)beagraphofordernandCbeacycleinG.Ciscalledadominatingcycle,orbrieflyaD--cycle,ifV(G)\V(C)isanindependentsetinG.ForavertexvinG,theneighborhoodofvisdenotedbyN(v),andthedegreeofvisdenotedbyd(v).FortwosubsetsSandTofV(G),wesetNT(S)~{vET\S:N(v)nS/0}.WewriteN(u,v)insteadofNV(G)({u,v})foranyu,vEV(G).IfFandHaretwosubgraphsofG,wealsowriteNF(H)insteado…     

THE CONNECTIVITY OF MAXIMUM MATCHING GRAPHS

The maximum matching graph of a graph has a vertex for each maximummatching and an edge for each pair of maximum matchings which differ by exactly oneedge. In this paper, we prove that the connectivity of maximum matching graph of abipartite graph is equal to its minimum degree.     

A NOTE ON COMPLETELY POSITIVE GRAPHS

1. IlltroductionPioneered by M. Hall Jr. in 195811] and investigated by A. Berman [2--4] and J. H. Drew, C.R. Johnson and Loewy[5] et al., completely positive matrices have been shown their importancenot only in the study of block designs in combinatorial analysis[6], but also in establishingeconomic model.[7].Recall that an n x n matrix A is said to be completely positive, denoted by A E CPu, ifthere edest m nonnegative column vectors hi,'', ba such thatwhere I denotes transpose. The …     

HOMOMORPHISMS OF GENERALIZED DE BRUIJN-GOOD GRAPHS

In the paper the homomorphisms of generalized de Bruijn-Good graphs aredescribed in detail and all homomorphisms of de Bruijn-Good graphs are giveu as anexample.     

VERTEX-PRIMITIVE 1/2-TRANSITIVE GRAPHS

ＶＥＲＴＥＸ－ＰＲＩＭＩＴＩＶＥ１／２－ＴＲＡＮＳＩＴＩＶＥＧＲＡＰＨＳ￥ＤＵＳｈａｏｆｅｉ（ＤｅｐｏｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ，ＳｈａｎｘｉＵｎｉｖｅｒｓｉｔｙ，Ｔａｉｙｕａｎ０３０００６，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：Ｉｎｔｈｉｓｐａ...     

A LOCALIZATION CONDITION FORBIPANCYCLIC BIPARTITE GRAPHS

1.IntroductionThefollowingNash--william'stheoremtellsusthatthehamiltonianproblemconcerningbipartitegraphsisimportant,thoughwedonotseemuchliteratureonit.Theorem111]Thejollowingproblemsareequivalent:1)thedete~inationofallhamiltoniangmphs,2)thedete~inationof…     

THE LINEAR ARBORICITY OF COMPOSITION GRAPHS

The linear arboricity la(G) of a graph G is the minimum number of linear forests which partition the edges of G. Akiyama, Exoo and Harary conjectured that la(G) = [△(G) 1/2] for any regular graph G. In this paper, we prove the conjecture for some composition graphs, in particular, for complete multipartite graphs.     

PANCONNECTIVITY AND 2-CONNECTED CLAW-FREE GRAPHS

ＰＡＮＣＯＮＮＥＣＴＩＶＩＴＹＡＮＤ２－ＣＯＮＮＥＣＴＥＤＣＬＡＷ－ＦＲＥＥＧＲＡＰＨＳ￥ＧＡＯＪｉｎｇｚｈｅｎ（ＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ，ＳｈａｄｄｏｃｋＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，Ｊｉｎａｎ２５００１４，Ｃｈｉｎａ）Ｚ...     

A NEIGHBORHOOD UNION CONDITION FOR PANCYCLIC GRAPHS

1.IntroductionWeconsideronlysimplefinitegraphs.OurbasicnotationandterminologynotdefinedherefollowthOSeofBondyandMurtyll].ForagraphG,letV(G)andE(G)(orjustVandE)deDOtelievertexsetandedgeset,respectively.Wedenoteapathandacyclecontaining8veniCesbyPaandCarespectively.ThecycleCaiscalledans-cycle.Denotebyg(G)(orbrieflybyg)thegirthofG1.SetNC=min{IN(u)UN(v)l:tv相似文献   

HAJóS'''' CONJECTURE AND CONNECTIVITY OF EULERIAN GRAPHS

Hajos' conjecture asserts that a simple eulerian graph on n vertices can be decomposed into at most n-1/2 circuits. In this paper, we propose a new conjecture which is equivalent to Hajos' conjecture, and show that to prove Hajos' conjecture, it is sufficient to prove this new conjecture for 3-connected graphs. Furthermore, a special 3-cut is considered also.     

ON THE CONNECTIVITY OF CAYLEY COLOR GRAPHS

In this paper we obtain the necessary and sufficient condition for the connec-tivity of the Cayley color graphs or the Cayley graphs to be equal to their minimum degree.The sharp lower bounds of connectivity of Cayley color graphs and the Cayley graphs arealso obtained. Our results generalize the previous results obtained in [1] to [3].     

LONGEST CYCLES IN 2-CONNECTEDCLAW-FREE GRAPHS

1.IntroductionWeuse[1]forterminologyandnotationsnotdefinedhereandconsidersimplegraphsonly.FOragraphG,wedenotebyV(G)thevertexsetofG,byE(G)theedgesetofG.ForanyxEV(G),AgV(G),BgV(G)--AandanysubgraphSofG,weputDenotebyG[A]thesubgraphofGinducedbyA.LetCbeacycleof…     

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.     

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.