Graphs with special neighbourhood orderings of vertices
type: Item
instance of: scholarly article
title: Graphs with special neighbourhood orderings of vertices
zbMATH Open document ID: 0785.05080
DOI: 10.1016/0012-365X(93)90531-W
author: Halina Bielak
published in: Discrete Mathematics
publication date: 1994-04-18T00:00:00Z
review text: For a simple graph \(G\) let \(d(x,z)\) be the length of a shortest path connecting \(x\) and \(z\) in \(G\). Let \(N^ i(x)=\{z\in V(G): d(x,z)=i\}\), \(i=1,2\), and \(N^ 3(x)=\{z\in V(G): d(x,z)\in \{1,2\}\}\). Write \(x\prec_ i y\) iff \(N^ i(x)\subseteq N^ i(y)\cup\{y\}\). It is proved that no graph \(G\) can contain a subset \(\{v_ 1,\dots,v_ n\}\subseteq V(G)\), \(3\leq n\leq | V(G)|\), such that \(v_ j\succ_ i v_{j+1}\) and \(v_{j+1}\not\succ_ i v_ j\), \(j=1,\dots,n\) and \(i=1\) and 3. On the other hand, in the case \(i=2\) there exists an infinite family of such graphs. Finally, a relation to cotolerance graphs is discussed.
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 06F99
Mathematics Subject Classification ID: 06A06
zbMATH DE Number: 473109
zbMATH Keywords: neighbourhood orderings
zbMATH Keywords: perfectly orderable graph
zbMATH Keywords: preorder
zbMATH Keywords: cotolerance graphs
reviewed by: Konrad Engel
MaRDI profile type: Publication
cites work: Q3977497
cites work: Q3347930
cites work: Four classes of perfectly orderable graphs
cites work: Generalized neighbourhoods and a class of perfectly orderable graphs
cites work: Tolerance graphs
description: scientific article; zbMATH DE number 473109