Nordhaus-Gaddum bounds for locating domination
From MaRDI portal
Publication:2441609
DOI10.1016/J.EJC.2013.04.009zbMATH Open1284.05197arXiv1207.2142OpenAlexW2056981618MaRDI QIDQ2441609FDOQ2441609
Authors: C. Hernando, Mercè Mora, I. M. Pelayo 
Publication date: 25 March 2014
Published in: European Journal of Combinatorics (Search for Journal in Brave)
Abstract: A dominating set S of graph G is called metric-locating-dominating if it is also locating, that is, if every vertex v is uniquely determined by its vector of distances to the vertices in S. If moreover, every vertex v not in S is also uniquely determined by the set of neighbors of v belonging to S, then it is said to be locating-dominating. Locating, metric-locating-dominating and locating-dominating sets of minimum cardinality are called b-codes, e-codes and l-codes, respectively. A Nordhaus-Gaddum bound is a tight lower or upper bound on the sum or product of a parameter of a graph G and its complement G. In this paper, we present some Nordhaus-Gaddum bounds for the location number b, the metric-location-number e and the location-domination number l. Moreover, in each case, the graph family attaining the corresponding bound is characterized.
Full work available at URL: https://arxiv.org/abs/1207.2142
Recommendations
Cites Work
- Title not available (Why is that?)
- Complement reducible graphs
- Resolvability in graphs and the metric dimension of a graph
- Graphs \& digraphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Towards a theory of domination in graphs
- Locating-dominating codes: bounds and extremal cardinalities
- A survey of Nordhaus-Gaddum type relations
- Extremal graph theory for metric dimension and diameter
- Title not available (Why is that?)
- Title not available (Why is that?)
- Nordhaus-Gaddum for treewidth
- Nordhaus-Gaddum bounds for total domination
Cited In (22)
- LD-graphs and global location-domination in bipartite graphs
- GLOBAL LOCATION-DOMINATION IN THE LEXICOGRAPHIC PRODUCT AND CORONA OF GRAPHS
- \( [ 1 , 2 ]\)-dimension of graphs
- The difference between the metric dimension and the determining number of a graph
- Locating-dominating codes: bounds and extremal cardinalities
- Locating-domination and identification
- Resolving dominating partitions in graphs
- Locating domination in bipartite graphs and their complements
- Metric-locating-dominating sets of graphs for constructing related subsets of vertices
- Fault tolerant detectors for distinguishing sets in graphs
- Open-independent, open-locating-dominating sets
- Fault-tolerant detectors for distinguishing sets in cubic graphs
- Neighbor-locating coloring: graph operations and extremal cardinalities
- Locating-dominating sets in twin-free graphs
- On the binary locating-domination number of regular and strongly-regular graphs
- On metric-location-domination number of graphs
- A note on locating-dominating sets in twin-free graphs
- Neighbor-locating colorings in graphs
- On redundant locating-dominating sets
- On global location-domination in graphs
- Global location-domination in the join and Cartesian product of graphs
- Complexity results on open-independent, open-locating-dominating sets in complementary prism graphs
This page was built for publication: Nordhaus-Gaddum bounds for locating domination
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2441609)
