Ramsey numbers r(K_(1, 4), G) for all three-partite graphs G of order six

In this paper, we use a combinatorial analysis method. In the complete graph K N with edges colored arbitrarily by red or blue, we consider the proposition of the subgraph of the red graph or blue graph induced by the neighborhood of some vertex in V(K N). Inspired by the main results of Jayawardene and Rousseau (Ars Combinatoria, 2000, 163-173), we determine the Ramsey numbers of r(K 1, 4, G), where G is the three-partite graph of order six without isolate vertex.

Maximum Number of Edges of (rK_t)-Free Graphs

With positive integers r,t and n,where n≥rt and t≥2,the maximum number of edges of a simple graph of order n is estimated,which does not contain r disjoint copies of K_r for r=2 and 3.

Asymptotic upper bounds for wheel:complete graph Ramsey numbers

It is shown that r(W_m, K_n)≤(1+o(1))C_1n log n 2m-2m-2 for fixed even m≥4 and n→∞, and r(W_m, K_n)≤(1+o(1))C_2n 2mm+1 log n m+1m-1 for fixed odd m≥5 and n→∞, where C_1=C_1(m)>0 and C_2=C_2(m)>0, in particular, C_2=12 if m=5 . It is obtained by the analytic method and using the function f_m(x)=∫ 1 _ 0 (1-t) 1m dtm+(x-m)t , x≥0 , m≥1 on the base of the asymptotic upper bounds for r(C_m, K_n) which were given by Caro, et al. Also, cn log n 52 ≤r(K_4, K_n)≤(1+o(1)) n 3 ( log n) 2 (as n→∞ ). Moreover, we give r(K_k+C_m, K_n)≤(1+o(1))C_5(m)n log n k+mm-2 for fixed even m≥4 and r(K_k+C_m, K_n)≤(1+o(1))C_6(m)n 2+(k+1)(m-1)2+k(m-1) log n k+2m-1 for fixed odd m≥3 (as n→∞ ).

Circular L(j,k)-labeling numbers of trees and products of graphs

Let j, k and m be three positive integers, a circular m-L（j, k）-labeling of a graph G is a mapping f： V（G）→{0, 1, …, m-1}such that f（u）-f（v）m≥j if u and v are adjacent, and f（u）-f（v）m≥k if u and v are at distance two,where a-bm=min{a-b,m-a-b}. The minimum m such that there exists a circular m-L（j, k）-labeling of G is called the circular L（j, k）-labeling number of G and is denoted by σj, k（G）. For any two positive integers j and k with j≤k,the circular L（j, k）-labeling numbers of trees, the Cartesian product and the direct product of two complete graphs are determined.

CIRCULAR CHROMATIC NUMBER AND MYCIELSKI GRAPHS

For a general graph G, M（G） denotes its Mycielski graph. This article gives a number of new sufficient conditions for G to have the circular chromatic number xc（M（G）） equals to the chromatic number x（M（G））, which have improved some best sufficient conditions published up to date.

The Circular Chromatic Number of Some Special Graphs

The circular chromatic number of a graph is a natural generalization of the chromatic number. Circular chromatic number contains more information about the structure of a graph than chromatic number does. In this paper we obtain the circular chromatic numbers of special graphs such as C t k and C t k-v, and give a simple proof of the circular chromatic number of H m,n .

Circular Chromatic Numbers of Some Distance Graphs

The circular chromatic number of a graph is an important parameter of a graph. The distance graph G(Z,D) , with a distance set D , is the infinite graph with vertex set Z={0,±1,±2,...} in which two vertices x and y are adjacent iff y-x∈D . This paper determines the circular chromatic numbers of two classes of distance graphs G(Z,D m,k,k+1 ) and G(Z,D m,k,k+1,k+2 ).

NOTE ON CALCULATING WIENER NUMBERS OF MOLECULAR GRAPHS WITH SYMMETRY

The authors provided a simple method for calculating Wiener numbers of molecular graphs with symmetry in 1997.This paper intends to further improve on it and simplifies the calculation of the Wiener numbers of the molecular graphs.

EDGE-FACE CHROMATIC NUMBER OF 2-CONNECTED PLANE GRAPHS WITH HIGH MAXIMUM DEGREE

The edge-face chromatic number Xef （G） of a plane graph G is the least number of colors assigned to the edges and faces such that every adjacent or incident pair of them receives different colors. In this article, the authors prove that every 2-connected plane graph G with △（G）≥｜G｜ - 2≥9 has Xef（G） = △（G）.

Some results on circular chromatic number of a graph

For two integers k and d with （k, d） = 1 and k≥2d, let G^dk be the graph with vertex set {0,1,…k - 1 } in which ij is an edge if and only if d≤｜ i -j I｜≤k - d. The circular chromatic number χc（G） of a graph G is the minimum of k/d for which G admits a homomorphism to G^dk. The relationship between χc（ G- v） and χc （G）is investigated. In particular, the circular chromatic number of G^dk - v for any vertex v is determined. Some graphs withx χc（G - v） =χc（G） - 1 for any vertex v and with certain properties are presented. Some lower bounds for the circular chromatic number of a graph are studied, and a necessary and sufficient condition under which the circular chromatic number of a graph attains the lower bound χ- 1 ＋ 1/α is proved, where χ is the chromatic number of G and a is its independence number.

Bondage Number of 1-Planar Graph

The bondage number of a nonempty graph G is the cardinality of a smallest set of edges whose removal from G results in a graph a domination number greater than the domination number of G. In this paper, we prove that for a 1-planar graph G.

ON THE CROSSING NUMBER OF THE COMPLETE TRIPARTITE GRAPH K_(1,8,n)

The well known Zarankiewicz' conjecture is said that the crossing number of the complete bipartite graph Km,n (m≤n) is Z(m,n). where Z(m,n) = [m/2] [(m-1)/2] [n/2] [(n-1)/2](for and real number x, [x] denotes the maximal integer no more than x). Presently, Zarankiewicz' conjecture is proved true only for the case m≤G. In this article, the authors prove that if Zarankiewicz' conjecture holds for m≤9, then the crossing number of the complete tripartite graph K1,8,n is Z(9, n) + 12[n/2].

Bondage and Reinforcement Number of γ_f for Complete Multipartite Graph

The bondage number of γ f, b f(G) , is defined to be the minimum cardinality of a set of edges whose removal from G results in a graph G′ satisfying γ f(G′)> γ f(G) . The reinforcement number of γ f, r f(G) , is defined to be the minimum cardinality of a set of edges which when added to G results in a graph G′ satisfying γ f(G′)< γ f(G) . G.S.Domke and R.C.Laskar initiated the study of them and gave exact values of b f(G) and r f(G) for some classes of graphs. Exact values of b f(G) and r f(G) for complete multipartite graphs are given and some results are extended.

The multi--intersection number of a graph

The intersection number, in (G), has been defined as the minimumcardinality of a set S which has n different subsets S_i such that each S_i can beassigned to the node v_i of G and nodes v_i, v_j are adjacent if and onlyif S_i∩S_j ≠0. We introduce the multiset intersection number min (G), defined similarly exceptthat multisets with elements in S may now be assigned to the nodes of G. Weprove that min (G) equals the smallest number ofcliques of G whose union is G.

On Locating Numbers of Graphs

Let G =( V,E) be a connected graph and W = { w_1,w_2,…,w_k} be an ordered subset of V( G).For any vertex v ∈V,the locating code of v with respect to W is the k-vector CW( v) = { d( v,w_1),d( v,w_2),…,d( v,w_k) },W is said to be a locating set of G if distinct vertices have the distinct locating code,and the locating number of G is defined as: Loc( G) = min{ | W| : W is a locating set of G}.We study the locating set and locating number of a graph G,obtain some bounds for the locating numbers of graphs,and determine the exact value of Loc( G) for some special classes of graphs,such as cycles,wheels,complete t-partite graph and some Cartesian products of paths and cycles. In addition,we also prove that Loc( T) ≥Δ-1 holds for all trees T with maximum degree Δ,and shows a tree T with Loc( T) = Δ-1.

ENTIRE CHROMATIC NUMBER AND Δ-MATCHING OF OUTERPLANE GRAPHS

Let G be an outerplane graph with maximum degree A and the entire chromatic number Xvef（G）. This paper proves that if △ ≥6, then △＋ 1≤Xvef（G）≤△＋ 2, and Xvef （G） = △＋ 1 if and only if G has a matching M consisting of some inner edges which covers all its vertices of maximum degree.

The Total Irredundance Numbers on Graphs

This paper discusses the total irredundance relations between the graph G and its clone-contraction graph H, that is, let H be the clone-contraction graph of G and v1,v2,...,vk be all contraction vertices ofH. IfS is a maximal total irredundant set of H such that A = S ∩ {V1,V2,…,Vk} contains as few vertices as possible, then S＇= S-A is the maximal total irredundant set of G. Furthermore, we obtain the bound of the total irredundance A（G） number： irt ≤△（G）/2△（G）＋1 n, which n is the order of graph G, and △（G） is maximum degree in G.

CHROMATIC NUMBER OF SQUARE OF MAXIMAL OUTERPLANAR GRAPHS

Let x（G^2） denote the chromatic number of the square of a maximal outerplanar graph G and Q denote a maximal outerplanar graph obtained by adding three chords y1 y3, y3y5, y5y1 to a 6-cycle y1y2…y6y1. In this paper, it is proved that △ ＋ 1 ≤ x（G^2） ≤△ ＋ 2, and x（G^2） = A ＋ 2 if and only if G is Q, where A represents the maximum degree of G.

The Crossing Number of Cartesian Products of Stars with 5-vertex Graphs II

The crossing number of cartesian products of paths and cycles with 5-vertex graphs mostly are known, but only few cartesian products of 5-vertex graphs with star K 1,n are known. In this paper, we will extent those results, and determine the crossing numbers of cartesian products of two 5-vertex graphs with star K 1,n .

STABILITY NUMBER IN SUBCLASSES OF P_5^-FREE GRAPHS

Two new hereditary classes of P 5-free graphs where the stability number can be found in polynomial time are proposed.They generalize several known results.