Paths in r-partite self-complementary graphs

✍ Scribed by T. Gangopadhyay; S.P. Rao Hebbare

• Publisher: Elsevier Science
• Year: 1980
• Tongue: English
• Weight: 683 KB
• Volume: 32
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(80)90261-7

✦ Synopsis

It is shown that. every connected bi-p.s.c, graphs G(2I of order p. with a bi-partite complementing permutation (bi-p.e.p) o" having mixed cycles, has a (p-3)-path and this result is best possible. Further. if the graph induced on each cycle of bi-p.c.p, of G( 2) is connected then G(2) has a hamiltonian path. Lastly the fact that every r-p.s.c, graph with an r-partite complementi:~.,'.' permutation Ir-p.c.p.) o" which permutes the partitions and for which each cycle of <r has non-empty intersection with at least four partitions of G(r), has a hamiltonian path, is established. The graph obtai,~ed from G(r) by adding a vertex u constituting (r+ t)-st partition of G(rL which is the fixed peint of or* = (u)o-also has a hamiltonian path. The last two res'dts generalize the result that every self-complementary graph has a hamiltonian path.