| Identifikační kód | RIV/00216224:14330/11:00053105 |
|---|
| Název v anglickém jazyce | Parameterized Problems Related to Seidel's Switching |
|---|
| Druh | J - Článek v odborném periodiku |
|---|
| Jazyk | eng - angličtina |
|---|
| Obor - skupina | B - Fyzika a matematika |
|---|
| Obor | BA - Obecná matematika |
|---|
| Rok uplatnění | 2011 |
|---|
| Kód důvěrnosti údajů | S - Úplné a pravdivé údaje o výsledku nepodléhající ochraně podle zvláštních právních předpisů. |
|---|
| Počet výskytů výsledku | 2 |
|---|
| Počet tvůrců celkem | 4 |
|---|
| Počet domácích tvůrců | 1 |
|---|
| Výčet všech uvedených jednotlivých tvůrců | Petr Hliněný (státní příslušnost: CZ - Česká republika, domácí tvůrce: A, vedidk: 7595646)
Eva Jelínková (státní příslušnost: CZ - Česká republika)
Jan Kratochvíl (státní příslušnost: CZ - Česká republika)
Ondřej Suchý (státní příslušnost: CZ - Česká republika) |
|---|
| Popis výsledku v anglickém jazyce | Seidel's switching is a graph operation which makes a given vertex adjacent to precisely those vertices to which it was non-adjacent before, while keeping the rest of the graph unchanged. Two graphs are called switching-equivalent if one can be made isomorphic to the other by a sequence of switches. In this paper, we continue the study of computational complexity aspects of Seidel's switching, concentrating on Fixed Parameter Complexity. Among other results we show that switching to a graph with at most$k$ edges, to a graph of maximum degree at most $k$, to a $k$-regular graph, or to a graph with minimum degree at least $k$ are fixed parameter tractable problems, where $k$ is the parameter. On the other hand, switching to a graph that contains a givenfixed graph as an induced subgraph is $W[1]$-complete. We also show the NP-completeness of switching to a graph with a clique of linear size, and of switching to a graph with small number of edges. |
|---|
| Klíčová slova oddělená středníkem | graph; Seidel switching |
|---|
| Stránka www, na které se nachází výsledek | - |
|---|