On the lengths of symmetry breaking-preserving games on graphs

DOI10.1016/J.TCS.2002.10.003MaRDI QIDQ1885002zbMATH OpenOpenAlexFDO

Authors Frank Harary, Wolfgang Slany, Oleg Verbitsky

Publication date 27 October 2004

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0401363

zbMATH Keywords

Ehrenfeucht-Fraïssé game

Mathematics Subject Classification ID

Basic properties of first-order languages and structures (03C07) Graph algorithms (graph-theoretic aspects) (05C85) Games involving graphs (91A43)

Abstract: Given a graph $G$, we consider a game where two players, $A$ and $B$, alternatingly color edges of $G$ in red and in blue respectively. Let $l(G)$ be the maximum number of moves in which $B$ is able to keep the red and the blue subgraphs isomorphic, if $A$ plays optimally to destroy the isomorphism. This value is a lower bound for the duration of any avoidance game on $G$ under the assumption that $B$ plays optimally. We prove that if $G$ is a path or a cycle of odd length $n$, then $Omega(logn)lel(G)leO(lo{g}^{2}n)$. The lower bound is based on relations with Ehrenfeucht games from model theory. We also consider complete graphs and prove that $l(K_n)=O(1)$.

Recommendations

• scientific article; zbMATH DE number 1944410
• scientific article; zbMATH DE number 2124072
• The Ehrenfeucht-Fraïssé game for paths and cycles.
• scientific article; zbMATH DE number 1076137
• scientific article; zbMATH DE number 969183

Cites work

• scientific article; zbMATH DE number 3885959 (Why is no real title available?)
• scientific article; zbMATH DE number 3900800 (Why is no real title available?)
• scientific article; zbMATH DE number 1324669 (Why is no real title available?)
• scientific article; zbMATH DE number 1944410 (Why is no real title available?)
• Parallel concepts in graph theory
• The strange logic of random graphs

Cited in

(2)

• Pairings and related symmetry notions
• scientific article; zbMATH DE number 1944410 (Why is no real title available?)

This page was built for publication: On the lengths of symmetry breaking-preserving games on graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1885002)