Search

In this paper, some properties of Ramsey numbers are studied, and the following results are presented. 1. (1) For any positive integers k1, k2, …, km l1, l2, …, lm (m > 1), we have r ∏i=1m ki + 1, ∏i=1m li + 1 ≥ ∏i=1m [ r (ki + 1,li + 1) − 1] + 1 . 2. (2) For any positive integers k1, k2, …, km, l1, l2, …, ln , we have r ∑i=1m ki + 1, ∑j=1n lj + 1 ≥ ∑i=1m∑j=1n r (ki + 1,lj + 1) − mn + 1 . Based on the known results of Ramsey numbers, some results of upper bounds and lower bounds of Ramsey numbers can be directly derived by those properties.

Let G = (V, E) be a graph. For a function f : V → {−1, 1}, the weight of f is w(f) = Σv ∈ V f(v). For a vertex v in V, we define f[v] = Σu∈N[v] f(u). A signed dominating function of G is a function f : V → {−1, 1} such that f[v] ⩾ 1 for all v ∈ V. The signed domination number γs(G) of G is the minimum weight of a signed dominating function on G. A signed dominating function of a weight γs(G) we call a γs-function of G. In this paper, we study the signed domination problem of general graph, and obtain some lower bounds of the signed domination number of a graph, and show that these lower bounds are sharp, and extend a result in Dunbar et al. (1995).

In this paper, we prove that χT ( G ) = 5 for any Halin graph G with Δ ( G ) = 4, where Δ ( G ) and χT ( G ) denote the maximal degree and the total chromatic number of G , respectively.

LetG be a planar graph with δ(G)≥3,f 0 be a face ofG. In this paper it is proved that for any Halin graph with Δ(G)≥6,x c (G)=Δ(G)+1, where Δ(G),x c (G) denote the maximum degree and the complete chromatic number ofG, respectively.

In this paper, the following results are obtained: a(G) + β(G) ⩽ p + 1, ⌈p2⌉ ⩽ a(G)β(G), ⌈p2⌉ ⩽ a′(G) + gb′(Ḡ) ⩽ pa′(G) + α′(Ḡ) ⩽ 2⌈p2⌉ (δ ⩽ 1) and all bounds are sharp, where p = ¦V(G)¦, ⌈x⌉ denotes the smallest integer greater than or equal to x, a(G) is the vertex arboricity, a′(G) is the edge arboricity, α′(G) is the edge covering number, β(G) is the vertex independent number, β′(G) is the edge independent number, and δ is the minimum degree of G.

For a graph G(V, E), if a proper k-edge coloring ƒ is satisfied with C(u) ≠ C(v) for uv ∈ E(G), where C(u) = {ƒ(uv) | uv ∈ E} , then ƒ is called k-adjacent strong edge coloring of G, is abbreviated k-ASEC, and χ′as(G) = min{k | k-ASEC of G} is called the adjacent strong edge chromatic number of G. In this paper, we discuss some properties of χ′as(G), and obtain the χ′as(G) of some special graphs and present a conjecture: if G are graphs whose order of each component is at least six, then χ′as(G) ≤ Δ(G) + 2, where Δ(G) is the maximum degree of G.