Induced paths in twin-free graphs
type: Item
instance of: scholarly article
title: Induced paths in twin-free graphs
zbMATH Open document ID: 1160.05316
author: David Auger
published in: The Electronic Journal of Combinatorics
publication date: 2009-04-07T00:00:00Z
full work available at URL: https://eudml.org/doc/129818
full work available at URL: v15i1n17.html
review text: Summary: Let \(G=(V,E)\) be a simple, undirected graph. Given an integer \(r \geq 1\), we say that \(G\) is \(r\)-twin-free (or \(r\)-identifiable) if the balls \(B(v,r)\) for \(v \in V\) are all different, where \(B(v,r)\) denotes the set of all vertices which can be linked to \(v\) by a path with at most \(r\) edges. These graphs are precisely the ones which admit \(r\)-identifying codes. We show that if a graph \(G\) is \(r\)-twin-free, then it contains a path on \(2r+1\) vertices as an induced sugbraph, i.e. a chordless path.
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 5540879
zbMATH Keywords: r-twin-free graphs
zbMATH Keywords: r-identifiable
zbMATH Keywords: balls
zbMATH Keywords: chordless path
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 5540879