Observability of lattice graphs

DOI10.1007/S00453-015-0049-ZzbMATH Open1350.68212arXiv1505.02224OpenAlexW1816816559MaRDI QIDQ329291FDOQ329291

Authors: Fangqiu Han, Subhash Suri, Xifeng Yan 

Publication date: 21 October 2016

Published in: Algorithmica (Search for Journal in Brave)

Abstract: We consider a graph observability problem: how many edge colors are needed for an unlabeled graph so that an agent, walking from node to node, can uniquely determine its location from just the observed color sequence of the walk? Specifically, let G(n,d) be an edge-colored subgraph of d-dimensional (directed or undirected) lattice of size n^d = n * n * ... * n. We say that G(n,d) is t-observable if an agent can uniquely determine its current position in the graph from the color sequence of any t-dimensional walk, where the dimension is the number of different directions spanned by the edges of the walk. A walk in an undirected lattice G(n,d) has dimension between 1 and d, but a directed walk can have dimension between 1 and 2d because of two different orientations for each axis. We derive bounds on the number of colors needed for t-observability. Our main result is that Theta(n^(d/t)) colors are both necessary and sufficient for t-observability of G(n,d), where d is considered a constant. This shows an interesting dependence of graph observability on the ratio between the dimension of the lattice and that of the walk. In particular, the number of colors for full-dimensional walks is Theta(n^(1/2)) in the directed case, and Theta(n) in the undirected case, independent of the lattice dimension. All of our results extend easily to non-square lattices: given a lattice graph of size N = n_1 * n_2 * ... * n_d, the number of colors for t-observability is Theta (N^(1/t)).

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

Recommendations

• Observable graphs
• Asymptotic behaviour of the observability of \(Q_ n\)
• Landmarks in graphs
• scientific article; zbMATH DE number 907924
• scientific article; zbMATH DE number 1195778

zbMATH Keywords

orthogonal arraysedge coloringgraph observabilitylattice graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Collective dynamics of `small-world' networks
• Orthogonal arrays. Theory and applications
• An Introduction to Symbolic Dynamics and Coding
• Orthogonal Arrays of Index Unity
• Observability of Boolean networks: a graph-theoretic approach
• The small-world phenomenon: an algorithmic perspective
• Observability of discrete event dynamic systems
• Observable graphs

Cited In (2)

• Title not available (Why is that?)
• Observable graphs

This page was built for publication: Observability of lattice graphs

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