A generalization of a theorem of Diderrich in additive group theory to vertex-transitive graphs
type: Item
instance of: scholarly article
title: A generalization of a theorem of Diderrich in additive group theory to vertex-transitive graphs
zbMATH Open document ID: 0862.05047
author: Isabelle Salaün
published in: European Journal of Combinatorics
publication date: 1997-05-19T00:00:00Z
review text: Consider a vertex-transitive (finite) directed graph \(X=(V,E)\). Let \(\kappa (X)\) be its connectivity number in directed sense. As known, each indegree and each outdegree in \(X\) equals \(|E|/ |X|\). Denote this number by \(d\). It is shown that \(d= \kappa (X)\) if there is no transitive triangle in \(X\). Let a sequence \(X_i= (V,E_i)\) of directed graphs be given where \(i\) runs from 1 to \(k\). Assume that each of these graphs is vertex-transitive and contains no transitive triangle. For \(a\in V\) denote by \(\Lambda (a)\) the set of all vertices \(b\) satisfying the following requirement: there exist a number \(t(\leq k)\), an increasing sequence \((1\leq) i_1< i_2<\cdots <i_t (\leq k)\), and a path \(P\) of length \(t\) such that \(P\) leads from \(a\) to \(b\), and, for any \(j\), the \(j\)th edge of \(P\) belongs to \(E_{ij}\). It is proved that then either \(\Lambda (a)\) is included in the vertex set of a connected component of some \(X_i\) or \(|\Lambda (a) |> d_1+ d_2+ \cdots + d_k\) where \(d_i\) is the common semidegree in \(X_i\). A corollary about finite groups is deduced from this graph-theoretical theorem. The corollary is a refinement of Theorem 3 of \textit{G. T. Diderrich} in [Proc. Am. Math. Soc. 38, 443-451 (1973; Zbl 0266.20041)].
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C25
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 20D60
zbMATH DE Number: 944214
zbMATH Keywords: connectivity
reviewed by: A. Ádám
MaRDI profile type: Publication
full work available at URL: eujc.1996.0058
OpenAlex ID: W2082122181
DOI: 10.1006/EUJC.1996.0058
Recommended article: Q4878669
Recommended article: Vertices of small degree in critically \(n\)-connected digraphs
Recommended article: Q3999955
Recommended article: On Iterated Image Size for Point-Symmetric Relations
Recommended article: Generalized degree conditions for graphs with bounded independence number
Recommended article: Sufficient conditions for equality of connectivity and minimum degree of a graph
Recommended article: Disjoint directed cycles
Recommended article: Some approaches to a conjecture on short cycles in digraphs
Recommended article: Coin graphs, polyhedra, and conformal mapping
Recommended article: On some cyclic connectivity properties of directed graphs (examples and problems)
description: scientific article; zbMATH DE number 944214