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

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.     

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…     

1/2-TRANSITIVE GRAPHS ASSOCIATED WITH LINEAR GROUPS

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

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

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

MINIMUM FILL-IN PROBLEM OF GRAPHS

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

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.     

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].     

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.     

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.     

VERTEX-PRIMITIVE 1/2-TRANSITIVE GRAPHS

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

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.     

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…     

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相似文献   

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.     

A LOCALIZATION CONDITION FORBIPANCYCLIC BIPARTITE GRAPHS

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

Star Chromatic Numbers of Planar Graphs

１ＩｎｔｒｏｄｕｃｔｉｏｎＤｅｆｉｎｉｔｉｏｎ１．１Ｌｅｔｋ,ｄｂｅｎａｔｕｒａｌｎｕｍｂｅｒｓｓｕｃｈｔｈａｔｋ２ｄ,ａ（ｋ,ｄ）－ｃｏｌｏｒｉｎｇｏｆａｇｒａｐｈＧ＝（Ｖ,Ｅ）ｉｓａｍａｐｐｉｎｇｃ：Ｖ→Ｚｋ,ｓｕｃｈｔｈａｔｆｏｒｅａｃｈｅｄ...     

A NOTE ON THE PAPER "ON THE CONNECTIVITY OF CAYLEY COLOR GRAPHS

ＡＮＯＴＥＯＮＴＨＥＰＡＰＥＲ＂ＯＮＴＨＥＣＯＮＮＥＣＴＩＶＩＴＹＯＦＣＡＹＬＥＹＣＯＬＯＲＧＲＡＰＨＳ＂￥ＭＥＮＧＪｉｘｉａｎｇ；ＨＵＡＮＧＱｉｏｎｇｘｉａｎｇ（ＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ，ＸｉｎｉｉａｎｇＵｎｉｖｅｒｓｉｔｙ，...