Student se seznámí s pojmem (sigma,ro)-dominace a ambivalnece ve vztahu ke speciálním třídám grafů. Poté bude zkoumat, které malé množiny sigma a ro jsou ambivalentní pro chordální grafy (tj. kdy existuje chordální graf, který má dvě různé (sigma,ro)-dominující množiny).
References
Jan Kratochvíl, Paul D. Manuel, Mirka Miller: Generalized Domination in Chordal Graphs. Nord. J. Comput. 2(1): 41-50 (1995)
Petr Golovach, Jan Kratochvil: Generalized domination in chordal graphs, a complete dichotomy, to appear in LNCS, Springer, Proceedings of WG'07
Preliminary scope of work
Množina vrcholů $S$ grafu $G$ se nazývá $(\sigma,\rho)$-dominující, pokud pro každý vrchol $v\in S$ je $|S\cap N(v)|\in\sigma$ a pro každý vrchol $v\notin S$ platí $|S\cap N(v)|\in\rho$, přičemž $\sigma$ a $\rho$ jsou množiny nezáporných celých čísel. Je známo, že rozhodnout zda chordální graf obsahuje nějakou $(\sigma,\rho)$-dominující množinu je polynomiální (NP-úplné), pokud dvojice $(\sigma,\rho)$ je neambivalentní (ambivalentní), což dává úplnou dichotomii výpočetní složitosti tohoto problému (dvojice $(\sigma,\rho)$ je ambivalentní, pokud existuje chordální graf obsahující alespoň dvě různé $(\sigma,\rho)$-dominující množiny, jinak je neambivalentní). Strukturální popis ambivalentních (neambivalentních) dvojic není znám. Cílem je získat ce nejvíce výsledků o ambivalenci dvojic malých množin.
Preliminary scope of work in English
A set $S$ of vertices of a graph $G$ is called {\em $(\sigma,\rho)$-dominating} if for every vertex $v\in S$, $|S\cap N(v)|\in\sigma$, and for every $v\notin S$, $|S\cap N(v)|\in\rho$, where $\sigma$ and $\rho$ are sets of nonnegative integers. It is known that deciding if a chordal graph contains a $(\sigma,\rho)$-dominating set is polynomial (NP-complete) if the pair ($\sigma, \rho$) is non-ambivalent (ambivalent, respectively), and this provides a complete dichotomy of the computational complexity (the pair ($\sigma, \rho$) is ambivalent if there exists a chordal graph which contains at least two different ($\sigma, \rho$)-dominating sets, and non-ambivalent otherwise). A structural description of ambivalent pairs is not known. The goal is find as much as possible about pairs of small sets.
