Meyniel's conjecture on graphs of bounded degree | Zendy

Hosseini Seyyed Aliasghar | Zendy; Mohar Bojan | Zendy; Gonzalez Hermosillo de la Maza Sebastian | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Premium

Meyniel's conjecture on graphs of bounded degree

Author(s) -

Hosseini Seyyed Aliasghar,

Mohar Bojan,

Gonzalez Hermosillo de la Maza Sebastian

Publication year - 2021

Publication title -

journal of graph theory

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.164

H-Index - 54

eISSN - 1097-0118

pISSN - 0364-9024

DOI - 10.1002/jgt.22662

Subject(s) - mathematics , conjecture , combinatorics , bounded function , degree (music) , clique sum , discrete mathematics , maximal independent set , indifference graph , chordal graph , trapezoid graph , set (abstract data type) , 1 planar graph , graph , computer science , physics , mathematical analysis , acoustics , programming language

The game of Cops and Robbers is a well‐known pursuit‐evasion game played on graphs. It has been proved that cubic graphs can have arbitrarily large cop number c ( G ) , but the known constructions show only that the set { c ( G ) ∣ Gcubic} is unbounded. In this paper, we prove that there are arbitrarily large subcubic graphs G whose cop number is at least n 1 ∕ 2 − o ( 1 )where n = ∣ V ( G ) ∣ . We also show that proving Meyniel's conjecture for graphs of bounded degree implies a weaker version of Meyniel's conjecture for all graphs.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research