TRAVERSING A GRAPH IN GENERAL POSITION

DOI10.1017/S0004972723000102zbMATH Open1526.05041arXiv2209.12631OpenAlexW4320494457MaRDI QIDQ6090185FDOQ6090185

Authors: Sandi Klavžar, James Tuite, Ismael G. Yero 

Publication date: 14 November 2023

Published in: Bulletin of the Australian Mathematical Society (Search for Journal in Brave)

Abstract: Let $G$ be a graph. Assume that to each vertex of a set of vertices $SsubseteqV(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.

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

Recommendations

• scientific article; zbMATH DE number 3920516
• A general position problem in graph theory
• Graph Traversals as Universal Constructions
• Graph traversal and graph transformation
• scientific article; zbMATH DE number 1568936
• Navigating in a Graph by Aid of Its Spanning Tree
• Paths in graphs
• scientific article; zbMATH DE number 3911721
• scientific article; zbMATH DE number 4189769

zbMATH Keywords

Kneser graphunicyclic graphrobot navigationgeneral position setmobile general position numbermobile general position set

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph operations (line graphs, products, etc.) (05C76)

Cites Work

• On the extremal combinatorics of the Hamming space
• Domination in transitive colorings of tournaments
• Mutual visibility by luminous robots without collisions
• On general position sets in Cartesian products
• The general position problem on Kneser graphs and on some graph operations
• The general position number of Cartesian products involving a factor with small diameter
• Characterization of general position sets and its applications to cographs and bipartite graphs
• A general position problem in graph theory
• On the general position problem on Kneser graphs
• The general position number of the Cartesian product of two trees
• On the general position number of two classes of graphs

Cited In (5)

• Mutual-visibility problems on graphs of diameter two
• Graph Traversals as Universal Constructions
• General position polynomials
• Repeatedly applying the combinatorial Nullstellensatz for zero-sum grids to Martin Gardner's minimum no-3-in-a-line problem
• Extremal edge general position sets in some graphs

This page was built for publication: TRAVERSING A GRAPH IN GENERAL POSITION

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