TRAVERSING A GRAPH IN GENERAL POSITION

DOI10.1017/S0004972723000102MaRDI QIDQ6090185zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

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

Cited in

(12)

• Extremal edge general position sets in some graphs
• Mutual-visibility problems on graphs of diameter two
• Generalization of edge general position problem
• Lower general position sets in graphs
• On some extremal position problems for graphs
• Graph Traversals as Universal Constructions
• General position polynomials
• Mobile mutual-visibility sets in graphs
• Moving through Cartesian products, coronas and joins in general position
• Three algorithmic approaches to the general position problem
• Counting largest mutual-visibility and general position sets of glued t-ary trees
• Repeatedly applying the combinatorial Nullstellensatz for zero-sum grids to Martin Gardner's minimum no-3-in-a-line problem

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)