Plena dukolora grafeo

Plena dukolora grafeo
Plia nomo	Dukliko
Plena dukolora grafeo kun m=3, n=2
Verticoj	m+n
Lateroj	mn
Aŭtomorfioj	2m!n! se m=n, m!n! se m≠n

En grafeteorio, plena dukolora grafeo aŭ dukliko estas speciala speco 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 latero v₁v₂ en G.

Pro tio ke la grafeo estas dukolora, por ĉiuj du verticoj $v_1 \in V_1$ kaj $v_2 \in V_1$, latero v₁v₂ ne estas en G; ankaŭ por ĉiuj du verticoj $v_1 \in V_2$ kaj $v_2 \in V_2$, latero v₁v₂ ne estas en G.

Plena dukolora grafeo kun dispartigoj de ampleksoj |V₁|=m kaj |V₂|=n estas skribata kiel K_{{m, n}}.

Por ĉiu k, K_{{1, k}} estas nomata kiel stelo. La grafeo K_{{1, 3}} estas nomata kiel ungego.

Ekzemploj

K1,3

K2,3

K3,3

Propraĵoj

• Por donita 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 geediziĝ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)