This paper is devoted to the problem of on-line labelling of graph vertices by walking agent so that all vertices in the neighbourhood of the current vertex have different labels (i.e. deterministic labelling). This problem arises in the navigation of mobile robots using topological maps of an environment. Here, a method for deterministic labelling is proposed for an agent of two types differing by the size of the observed neighbourhood of the current vertex.
The paper is dedicated to methods of distinction of vertices in labeled graphs by an automaton walking on the graph and reading vertex labels. This problem arises in the navigation of mobile robots using topological maps of the environment. We propose construction and realization methods for distinguishing experiments with deterministic graphs based on checking the isomorphism of subgraphs generated by all vertices that are accessible from compared vertices.
By definition, the compact graph is a regular graph with the minimum diameter. In the paper, the compactness conditions are investigated for regular graphs with the length of a minimum cycle restricted.
This paper is devoted to some structural properties of prefractal graphs. A procedure for generating prefractal graphs is described. Upper and least bounds for the number of cutpoints and bridges in prefractal graphs are given.
Published
2011
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.