OLD trees with maximum degree three
type: Item
instance of: scholarly article
zbMATH Open document ID: 1300.05234
author: Suk J. Seo
author: Peter Slater
publication date: 2014-08-28T00:00:00Z
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68M10
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 6335664
zbMATH Keywords: distinguishing set
zbMATH Keywords: open-locating-dominating set
zbMATH Keywords: identifying code
zbMATH Keywords: case analysis
MaRDI profile type: Publication
title: OLD trees with maximum degree three
published in: Utilitas Mathematica
review text: Let \(G\) be a graph, and let \(\mathcal{S}=\{S_1, \dots, S_p\}\) (where, for all \(i \in [1, p],\) \(S_i \subset V(G)\)) be such that \(\bigcup_{i=1}^p S_i=V(G),\) then \(\mathcal{S}\) is a distinguishing set of \(G\) if, for every pair of vertices in \(V(G),\) some \(S_i\) contains exactly one of them. Several related notions have been defined. In particular, let \(S =\{w_1, \dots, w_q\}\) (where, for all \(i \in [1, q]\), \(w_i \in V(G)\)), \(S\) is an open-locating-dominating set of \(G\) if \(\{N(w_1), \dots, N(w_q)\}\) is a distinguishing set of \(G.\) Here, for a vertex \(v \in V(G)\), \(N(v)\) refers to its open neighbors, i.e., all the vertices adjacent to \(v\), excluding \(v\) itself.NEWLINENEWLINENEWLINELet \(\mathrm{OLD}(G)\) further denote the cardinality of a minimum open-locating-dominating set of a graph \(G\). It was previously shown that, for \(T_n\) (a tree of order \(n\)), \(\lceil n/2 \rceil+1 \leq \mathrm{OLD}(T_n) \leq n-1\).NEWLINENEWLINENEWLINEIn this paper, the authors show that, in the tree \(T_{2k}\) for which \(\mathrm{OLD}(T_{2k})=2k-1\), there exists only one vertex whose degree is 4. They further show, with a detailed case analysis, that \(\mathrm{OLD}(T_n) \leq (5/6)n\) for \(n \geq 8,\) with \(\Delta(T_n)=3.\) The above bound is actually sharp.
reviewed by: Zhizhang Shen
description: scientific article; zbMATH DE number 6335664