Plena dukolora grafeo

En grafeoteorio, plena dukolora grafeo aŭ dukliko estas speciala tipo de dukolora grafeo, ĉe kiu ĉiu vertico de la unua aro estas koneksa al ĉiu vertico de la dua aro.

Tiel, plena dukolora grafeo G = (V1 + V2, E) estas dukolora grafeo tia ke por ĉiuj du verticoj  kaj , estas eĝo v1v2 en E.

Pro tio ke la grafeo estas dukolora, por ĉiuj du verticoj  kaj , eĝo v1v2 ne estu en G; same por  kaj .

Plena dukolora grafeo kies dispartigoj havas vertic-nombrojn |V1|=m kaj |V2|=n estas skribata kiel K{m, n}.

Por ĉiu k, K{1, k} nomiĝas stelgrafeo.

 Ekzemploj 
 105x105px  K1,3 113x113px  K2,3 115x115px  K3,3

380x380ra|eta|La stelgrafeoj K1,3, K1,4, K1,5, kaj K1,6.

 Propraĵoj 
 Por dukolora grafeo, trovado de ĝia plena dukolora subgrafeo K{m, n} kun maksimuma kvanto de lateroj mn estas NP-plena problemo.
 Ebena grafeo ne povas enhavi K{3,3} kiel minoro; ekstere ebena grafeo ne povas enhavi K{3,2} kiel minoro (ĉi tio estas necesaj sed ne sufiĉaj kondiĉoj por ebeneco kaj ekstera ebeneco).
 Plena dukolora grafeo K{n, n} estas grafeo de Moore kaj (n, 4)-kaĝo.
 Plena dukolora grafeo K{m, n} havas vertican kovrantan nombron min {m, n} kaj lateran kovrantan nombron max {m, n}.
 Plena dukolora grafeo K{m, n} havas maksimuman sendependan aron de amplekso max {m, n}.
 Plena dukolora grafeo K{m, n} havas maksimuman kongruanton de amplekso min {m, n}.
 Plena dukolora grafeo K{n, n} havas pozitivan n-lateran kolorigon.
 Plena dukolora grafeo K{m, n} havas mn-1 nm-1 generantajn arbojn.
 La lastaj du rezultoj estas korolarioj de la geedziĝa teoremo se ĝi estas aplikita al k-regula dukolora grafeo.
 Plena dukolora grafeo K{n, n} aŭ K{n, n+1} estas grafeo de Turán.

 Vidu ankaŭ 
 Dukolora grafeo
 Kliko (grafeo)
 Nulgrafeo
 Plena grafeo
 Ciklo (grafeo)
 Vojo (grafeo)

Kategorio:Grafeteorio