Perfect product graphs

✍ Scribed by G. Ravindra; K.R. Parthasarathy

• Publisher: Elsevier Science
• Year: 1977
• Tongue: English
• Weight: 880 KB
• Volume: 20
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(77)90056-5

✦ Synopsis

in this paper perfectness of varicws products of graphs is considered. The Cartesmn pro&r+. I G, x G, is perfect iff it has no induced C,,, , B (n 3 2). BJ considering the various uufik~cn~ conditions for the latter condition. perfect Carresisn products are charactcrixd. Similarly prrfcct tenwr products G, A ti, are characterized and it is prosed that the composition G,[G,] is pcrfecr iif G, itnd ii3 are perfect. Perfectness of nnrmal products was studied in an cork paper In an earlier paper [4] one of the authors studied the perfectness of the normal prod;Jcts of graphs. Mere a sitnilar study of the perfectness of three other product% of graphs is undertaken. Only ordinary (finite, looplcss, undirected and without multiple edges) graphs arc considered. Let Gt = (VI, EJ and G2 = (Vr, Er) be any twu graphs. Tht products studied in this paper are defined as follows: The Ccrtesian producr G = G, x GZ has the vertex set V = V, x V, and w,H'~ E E for Wr = (u,, u,), w2 = (~2. 02) iff either (i) ut L= u2 and ul~2 E E?, or (ii) ulul E El and u1 = U& The ccvnpusifkm (lexicographic product) G = G,[G,] has the vertex set V -& x VZ and wlwzE E iff either (i) uIu2E E,, or (ii) U] = uz and ui~2 E E,. The tt?nswpraduct (conjkwrion) G = G, A Gr has the vertex set V = V, x V2 nnd WIWZE E iff 1~~65 Et and ufiurE Ez.