PASTIC Dspace Repository

On Ramsey numbers of path versus wheel-like graphs

Show simple item record

dc.contributor.author Ali, Kashif
dc.date.accessioned 2017-11-22T11:05:51Z
dc.date.accessioned 2020-04-14T20:01:01Z
dc.date.available 2020-04-14T20:01:01Z
dc.date.issued 2007
dc.identifier.uri http://142.54.178.187:9060/xmlui/handle/123456789/8492
dc.description.abstract The study of classical Ramsey numbers R(m, n) shows little progress in the last two decades. Only nine classical Ramsey numbers are known. This difficulty of finding the classical Ramsey numbers has inspired many people to study generalizations of classical Ramsey number. One of them is to determine Ramsey number R(G, H) for general graphs G and H (not necessarily complete). One of the most general results on graph Ramsey numbers is the establish- ment of a general lower bound by Chv ́atal and Harary [17] which is formulated as: R(G, H) ≥ (χ(H) − 1)(c(G) − 1) + 1, where G is a graph having no isolated vertices, χ(H) is the chromatic number of H and c(G) denotes the cardinality of large con- nected component of G. Recently, Surahmat and Tomescu [41] studied the Ramsey number of a combina- tion of path P n versus Jahangir graph J 2,m . They proved that R(P n , J 2,m ) = n+m−1 for m ≥ 3 and n ≥ (4m − 1)(m − 1) + 1. Furthermore, they determined that R(P 4 , J 2,2 ) = 6 and R(P n , J 2,2 ) = n + 1 for n ≥ 5. This dissertation studies the determination of Ramsey number for a combination of path P n and a wheel-like graph. What we mean by wheel-like graph, is a graph obtained from a wheel by a graph operation such as deletion or subdivision of the spoke edges. The classes of wheel-like graphs which we consider are Jahangir graph, generalized Jahangir graph and beaded wheel. First of all we evaluate the Ramsey number for path P n with respect to Jahangir graph J 2,m . We improve the result of Surahmat and Tomescu for m = 3, 4, 5 with n ≥ 2m + 1. Also, we determine the Ramsey number for disjoint union of k identical copies of path P n versus Jahangir graph J 2,m for m ≥ 2. Moreover, we determine the Ramsey number of path P n versus generalized Ja- hangir graph J s,m for different values of s, m and n. We also, evaluate the Ramsey number for combination of disjoint union of t identical copies of path versus general- ized Jahangir graph J s,m for even s ≥ 2 and m ≥ 3. At the end, we find the Ramsey number of path versus beaded wheel BW 2,m , i.e. R(P n , BW 2,m ) = 2n − 1 or 2n if m ≥ 3 is even or odd, respectively, provided n ≥ 2m 2 − 5m + 4. en_US
dc.description.sponsorship Higher Education Commission, Pakistan en_US
dc.language.iso en en_US
dc.publisher GC University Lahore, Pakistan en_US
dc.subject Natural Sciences en_US
dc.title On Ramsey numbers of path versus wheel-like graphs en_US
dc.type Thesis en_US


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search DSpace


Advanced Search

Browse

My Account