Cop number of partial cubes
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909831103774720 |
|---|---|
| author | Crawford, Nicholas Chenoweth, Vesna Iršič |
| author_facet | Crawford, Nicholas Chenoweth, Vesna Iršič |
| contents | The game of Cops and Robbers on graphs is a well-studied pursuit--evasion model whose central parameter, the cop number, captures the minimum number of pursuers required to guarantee capture of an adversary on a given graph. While the cop number has been determined for many classical graph families, relatively little is known about the important class of partial cubes, i.e., isometric subgraphs of hypercubes.
In this paper, we establish a lower bound for the cop number of partial cubes and present an upper bound on a subclass of partial cubes. Additionally, we improve these bounds for a particular family of partial cubes: Fibonacci cubes. These graphs are defined as induced subgraphs of hypercubes obtained by forbidding consecutive ones in binary strings. Beyond their natural combinatorial interest, Fibonacci cubes have connections to chemical graph theory, where they serve as models for resonance graphs of certain classes of polycyclic aromatic hydrocarbons. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_06832 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Cop number of partial cubes Crawford, Nicholas Chenoweth, Vesna Iršič Combinatorics 05C57, 05C12 The game of Cops and Robbers on graphs is a well-studied pursuit--evasion model whose central parameter, the cop number, captures the minimum number of pursuers required to guarantee capture of an adversary on a given graph. While the cop number has been determined for many classical graph families, relatively little is known about the important class of partial cubes, i.e., isometric subgraphs of hypercubes. In this paper, we establish a lower bound for the cop number of partial cubes and present an upper bound on a subclass of partial cubes. Additionally, we improve these bounds for a particular family of partial cubes: Fibonacci cubes. These graphs are defined as induced subgraphs of hypercubes obtained by forbidding consecutive ones in binary strings. Beyond their natural combinatorial interest, Fibonacci cubes have connections to chemical graph theory, where they serve as models for resonance graphs of certain classes of polycyclic aromatic hydrocarbons. |
| title | Cop number of partial cubes |
| topic | Combinatorics 05C57, 05C12 |
| url | https://arxiv.org/abs/2510.06832 |