Cop-Win Graphs with Maximum Capture-Time

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F10%3A10030346" target="_blank" >RIV/00216208:11320/10:10030346 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Cop-Win Graphs with Maximum Capture-Time

Popis výsledku v původním jazyce

We present an upper bound n?4 for the maximum length of a cop and robber game (the capture-time) on a cop-win graph of order n. This bound matches the known lower bound. We analyze the structure of the class of all graphs attaining this maximum and describe an inductive construction of the entire class. A cop and robber game is a two-player vertex-to-vertex pursuit combinatorial game where the players stand on the vertices of a graph and alternate in moving to adjacent vertices. Cop's goal is to capturethe robber by occupying the same vertex as the robber, robber's goal is to avoid capture.

Název v anglickém jazyce

Cop-Win Graphs with Maximum Capture-Time

Popis výsledku anglicky

We present an upper bound n?4 for the maximum length of a cop and robber game (the capture-time) on a cop-win graph of order n. This bound matches the known lower bound. We analyze the structure of the class of all graphs attaining this maximum and describe an inductive construction of the entire class. A cop and robber game is a two-player vertex-to-vertex pursuit combinatorial game where the players stand on the vertices of a graph and alternate in moving to adjacent vertices. Cop's goal is to capturethe robber by occupying the same vertex as the robber, robber's goal is to avoid capture.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

—

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)<br>S - Specificky vyzkum na vysokych skolach<br>O - Projekt operacniho programu

Rok uplatnění

2010

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Discrete Mathematics

ISSN

0012-365X

e-ISSN

—

Svazek periodika

310

Číslo periodika v rámci svazku

10-11

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

7

Strana od-do

—

Kód UT WoS článku

000276941600008

EID výsledku v databázi Scopus

—