2004/01/26 by Frank Harary, Harary, Frank, Wolfgang Slany +3
Computer Science · Mathematics · #05C38 #90D42 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #Logic (math.LO) #math.CO #math.LO #msc:05C38 #msc:90D42
paper · pdf · doi:10.48550/arxiv.math/0401363
20 pages
arxiv created 2004/01/26 · openalex publication_date 2004/01/26 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Ω(log n)≤ l(G)≤ O(log2 n). The lower bound is based on relations with Ehrenfeucht games from model theory. We also consider complete graphs and prove that l(Kn)=O(1).