Traversing a graph in general position
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929392486187008 |
|---|---|
| author | Klavžar, Sandi Krishnakumar, Aditi Tuite, James Yero, Ismael |
| author_facet | Klavžar, Sandi Krishnakumar, Aditi Tuite, James Yero, Ismael |
| contents | Let $G$ be a graph. Assume that to each vertex of a set of vertices $S\subseteq V(G)$ a robot is assigned. At each stage one robot can move to a neighbouring vertex. Then $S$ is a mobile general position set of $G$ if there exists a sequence of moves of the robots such that all the vertices of $G$ are visited whilst maintaining the general position property at all times. The mobile general position number of $G$ is the cardinality of a largest mobile general position set of $G$. In this paper, bounds on the mobile general position number are given and exact values determined for certain common classes of graphs including block graphs, rooted products, unicyclic graphs, Cartesian products, joins of graphs, Kneser graphs $K(n,2)$, and line graphs of complete graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2209_12631 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Traversing a graph in general position Klavžar, Sandi Krishnakumar, Aditi Tuite, James Yero, Ismael Combinatorics 05C12, 05C76 Let $G$ be a graph. Assume that to each vertex of a set of vertices $S\subseteq V(G)$ a robot is assigned. At each stage one robot can move to a neighbouring vertex. Then $S$ is a mobile general position set of $G$ if there exists a sequence of moves of the robots such that all the vertices of $G$ are visited whilst maintaining the general position property at all times. The mobile general position number of $G$ is the cardinality of a largest mobile general position set of $G$. In this paper, bounds on the mobile general position number are given and exact values determined for certain common classes of graphs including block graphs, rooted products, unicyclic graphs, Cartesian products, joins of graphs, Kneser graphs $K(n,2)$, and line graphs of complete graphs. |
| title | Traversing a graph in general position |
| topic | Combinatorics 05C12, 05C76 |
| url | https://arxiv.org/abs/2209.12631 |