Some parameters of graph and its complement

✍ Scribed by Shao-ji Xu

• Publisher: Elsevier Science
• Year: 1987
• Tongue: English
• Weight: 627 KB
• Volume: 65
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(87)90142-7

✦ Synopsis

In this paper, we have discussed the Nordhaus-Gaddum problems for diameter d, girth g, circumference c and edge covering number ill-We have both got the following results.
If both G and G are connected, then 4<~d+a~~ 6, then p+2<.c+~<.2p, 3(p-1)<~c.~<.p 2. If both G and G have no isolated vertex, then

2{12p}<<-fll+[~l <<-2p-2-[~p], [P/212<~fll.f31<~lT(p-1 ). p-l<~fl+#~2p-s, O<~fl.#<-{p-½s}[P-½S],

where p is the vertex number, s = min{a + b [ r(a + 1, b + 1) >p} and r(a + 1, b + 1) means the well-known Ramsey number. The graphs considered here are finite, undirected and simple. Let G be a graph, V and E be vertex set and edge set of G. Throughout this paper, we always denote vertex number of G by p, chromatic number by X, achromatic number by if, edge chromatic number by Xx, edge connectivity by )., connectivity by r, domination number by v, diameter by d, ~ by g, circumference by c, independent number by tr, edge independent number by trx, coveting number by fl, edge covering number by fix, the degree of vertex v by d(v) and the corresponding parameter of complement t~ of G by f. The symbols [a] = max{x Ix integer, x <~a}, {a} = min{x Ix integer, x ~>a} are also used. In [10], the famous Nordhaus-Gaddum theorem states 2vrp ~< Z + ~<p + 1, (P + 1~ 2 P~<X'X~<\ 2 ]"
Since then the relations of some parameters between a graph and its complement are continuously discussed, they are called Nordhaus-Gaddum problems.