SOME RESULTS ON CIRCULAR PERFECT GRAPHS AND PERFECT GRAPHS

An r-circular coloring of a graph G is a map f from V(G) to the set of open unit intervals of an Euclidean circle of length r, such that f(u) ∩ f(v) = Ф whenever uv ∈ E(G). Circular perfect graphs are defined analogously to perfect graphs by means of two parameters, the circular chromatic number and the circular clique number. In this paper, we study the properties of circular perfect graphs. We give (1) a necessary condition for a graph to be circular perfect, (2) some circular critical imperfect graphs, and (3) a characterization of graphs with the property that each of their induced subgraphs has circular clique number the same as its clique number, and then the two conjectures that are equivalent to the perfect graph conjecture.     

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…     

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.     

THE NORMALITY OF CAYLEY GRAPHS OF SIMPLE GROUP A_5 WITH SMALL VALENCIES

1.IntroductionLetGbeafinitegroup.ForaCayleysubsetSofGnotcontainingtheidentityelement1,theCayley(di)graphX~Cay(G,S)ofGwithrespecttoSisdefinedasthedirectedgraphwithvertexsetV(X)=GandedgesetE(X)={(g,sg)IgEG,s6S}.IfS=S--',thentheadjacencyrelationissymmet...     

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.     

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…     

VERTEX-PRIMITIVE 1/2-TRANSITIVE GRAPHS

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

A RELATION BETWEEN THE MATCHING NUMBER AND LAPLACIAN SPECTRUM OF A TREE

Let T be a tree with matching number μ(T). In this paper we obtain the following result: If T has no perfect matchings, thenμ(T) is a lower bound for the number of nonzero Laplacian eigenvalues of T which are smaller than 2.     

The projective plane crossing numbers of circular graphs*

The authors give an upper bound for the projective plane crossing number of a circular graph. Also, the authors prove the projective plane crossing numbers of circular graph C （8, 3） and C （9, 3） are 2 and 1, respectively.     

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.     

COMPARING THE INDEPENDENCE OF DIFFERENT RANDOM NUMBER GENERATORS

Pseudo-random number generators have always been important in experimental design, computer simulation, cryptography and statistical analysis. This paper presents a method of comparing the degree of independence exhibited by various random number generators, a procedure, based on consideration of the largest (in modulus) non-unit eigenvalue of the observed Markov transition matrix, is used to assess the ‘randomness‘ of a random number generator.     

(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 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 …     

EXACT VALUE OF THE HARMONIOUS CHROMATIC NUMBER OF A COMPLETE TRINARY TREE

1.IntroductionLetG={VE}beafinite,undirected,simplegraPh,TheharmoniouschromaticnumberofagraPhG,denotedbyh(G),istheleastnumber0fcolorsneededtocol0rtheverticesofGinsuchawaythatanytwoadacelitverticesarec0loredbydmerelltcol0rsandanytwodistinctedgeshavedtherentcolorpairs(Here,ac0lorpairforedgee=uvisthepairofcol0rsusedt0coloruandv).Theharmoniouscol0ringshavebeenstudiedinpaPersl1-10].J.Mitchem[10]0btainedtheexactvalue0ftheharm0ni0uschr0maticnUInber0fthepath,cycleandc0mpleten-nytreewith3or4levels…     

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…     

1/2-TRANSITIVE GRAPHS ASSOCIATED WITH LINEAR GROUPS

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

A NOTE ON CONNECTED FACTORS IN CLAW-FREE GRAPHS

1. IntroductionAll graphs considered here are finite and undirected, without loops or multiple edges. Thevertex set, edge set and the degree of a vertex v of a graph G are denoted, respectively, byV(G),E(G) and dG(v). For a set S G V(G) the subgraph of G induced by S is denoted byG[S].Let G be a graph, j and g positive integer Valued functions on V(G) with f(v) S g(v) 5dG(u) for all v 6 V(G). A spanmng SUbgraph F Of G is called an [f,g]-factor Of G if forall v E V(G), f(v) 5 dF(v…     

EDGE RECONSTRUCTION OF PLANAR GRAPHS WITH MINIMUM DEGREE AT LEAST THREE-(IV)

ＥＤＧＥＲＥＣＯＮＳＴＲＵＣＴＩＯＮＯＦＰＬＡＮＡＲＧＲＡＰＨＳＷＩＴＨＭＩＮＩＭＵＭＤＥＧＲＥＥＡＴＬＥＡＳＴＴＨＲＥＥ－（ＩＶ）￥ＦＡＮＨｏｎｇｂｉｎｇ（ＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ，ＳｈａｎｄｏｎｇＵｎｉｖｅｒｓｉｔｙ，Ｊｉ＇...     

CONNECTED [1, k]-FACTORS OF BALANCE BIPARTITE GRAPHS

1.IntroductionAllgraphsconsideredaresimpleandfinite.Wereferthereaderto[1]forstandardgraphterminologiesnotdefinedinthispaper.LetGbeagraphwithvertexsetV(G)andedgesetE(G).ForanySCV(G),wedenotebyNG(S)theneighborsetofSinG,anddefineNG[S]=NG(S)US.LetdG(v)denotethedegreeofvinG.IfwewriteG=(VI,VZ),itmeansthatGisabipartitegraphwiththepartition(VI,V2)ofV(G).IfIVII=IVZI,wecallGabalancebipartitegraph.LetafbbetwopositiveintegerssuchthataSb.AspanningsubgraphFofGiscalledan[a,b]-factorofGi…