2-Eksponen dari Digraph Dwiwarna Asimetrik yang memuat Cycle Primitif

Abstract

Suatu digraph dwiwarna adalah sebuah digraph dengan setiap arcnya terwarnai,merah atau biru. Sebuah digraph dwiwarna D dikatakan terhubung kuat bila ada bilangan tak negatif h dan k sehingga untuk setiap pasangan verteks u dan v ditemukan walk yang panjangnya h+k dengan h arc merah dan k arc biru. Bilangan bulat terkecil h+k dikatakan 2-eksponen dari D. Sebuah asimetrik digraph dwiwarna adalah sebuah simetrik digraph dwiwarna sedemikian bila (u, v) adalah arc merah maka (v, u) adalah arc biru, demikian sebaliknya. Sebuah digraph dwiwarna asimetrik yang mempunyai cycle primitif adalah sebuah digraph dwiwarna asimetrik dengan n verteks yang mempunyai cycle dengan panjang s dan path dengan panjang n − s yang terhubung dengan cycle dan tidak terhubung dengan cycle. Dalam tulisan ini ditunjukkan bahwa, sebuah digraph dwiwarna asimetrik yang memuat cycle primitif dengan panjang s ≥ 3 dan merupakan bilangan ganjil, memiliki 2 − exp(D) ≤ (s2 − 1)/2 + (s + 1)(n − s).