Plena dukolora grafeo

Plena dukolora grafeo
Plia nomo	Dukliko
Plena dukolora grafeo kun m=3, n=2
Dukolora grafeo • biregular graph • hamiltona grafo • cograph • chordal bipartite graph • graceful graph
Verticoj	m+n
Lateroj	mn
Aŭtomorfioj	2m!n! se m=n, m!n! se m≠n
v • d • r

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 ${\displaystyle v_{1}\in V_{1}}$ kaj ${\displaystyle v_{2}\in V_{2}}$, estas eĝo v₁v₂ en E.

Pro tio ke la grafeo estas dukolora, por ĉiuj du verticoj ${\displaystyle v_{1}\in V_{1}}$ kaj ${\displaystyle v_{2}\in V_{1}}$, eĝo v₁v₂ ne estu en G; same por ${\displaystyle v_{1}\in V_{2}}$ kaj ${\displaystyle 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.