Plena dukolora grafeo

Ŝablono: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 = (V₁ + V₂, E) estas dukolora grafeo tia ke por ĉiuj du verticoj $v_1\in V_1$ kaj $v_2\in V_2$, estas eĝo v₁v₂ en E.

Pro tio ke la grafeo estas dukolora, por ĉiuj du verticoj $v_1\in V_1$ kaj $v_2\in V_1$, eĝo v₁v₂ ne estu en G; same por $v_1\in V_2$ kaj $v_2\in V_2$.

Plena dukolora grafeo kies dispartigoj havas vertic-nombrojn |V₁|=m kaj |V₂|=n estas skribata kiel K_{{m, n}}.

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

Ekzemploj

K1,3

K2,3

K3,3

La stelgrafeoj K_1,3, K_1,4, K_1,5, kaj K_1,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 m^n-1 n^m-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)