The structure of neighbor disconnected vertex transitive graphs
type: Item
instance of: scholarly article
title: The structure of neighbor disconnected vertex transitive graphs
zbMATH Open document ID: 0936.05051
DOI: 10.1016/S0012-365X(98)00348-3
author: Richard Goldstone
published in: Discrete Mathematics
publication date: 2000-05-08T00:00:00Z
review text: The ideas of the main theorem are introduced by pointing out that a disconnected vertex transitive graph with \(t\) connected components is in fact a wreath product of a connected vertex transitive graph and an empty graph of order \(t\). Moreover, such a graph is the complement of a vertex transitive graph which becomes empty after the removal of the closed neighborhood of a vertex. A graph is neighbor disconnected if the removal of the closed neighborhood of a vertex leaves a disconnected induced subgraph. After defining wreath product inducers as a technical tool, several structure theorems are proven: A nonempty graph admitting a left action of a group \(G\) is vertex transitive and neighbor disconnected if and only if it has a nontrivial wreath product factorization in which both factors are vertex transitive for some subgroup of \(G\). As an application wreath product decompositions of all connected, neighbor disconnected vertex transitive graphs of degrees not exceeding 10 are given. Finally, necessary and sufficient conditions for neighbor disconnection in terms of neighborhoods and orbits of the vertex whose closed neighborhood is deleted are developed, giving a different perspective on neighborhood disconnection which is particularly useful for Cayley graphs defined in terms of generating subsets of the group.
reviewed by: Brigitte Servatius
Mathematics Subject Classification ID: 05C25
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 1334519
zbMATH Keywords: vertex transitive graph
zbMATH Keywords: Cayley graph
zbMATH Keywords: wreath product
zbMATH Keywords: neighbor connectivity
zbMATH Keywords: neighborhood connection
MaRDI profile type: Publication
cites work: Cayley Graphs with Neighbor Connectivity One
cites work: Neighbour-connectivity in regular graphs
cites work: Q3772256
cites work: Q4190671
cites work: The composition of graphs
description: scientific article; zbMATH DE number 1334519