×

zbMATH — the first resource for mathematics

On the connectivity of Cayley digraphs. (English) Zbl 0561.05028
L’auteur rappelle la définition et les propriétés des atomes et des fragments d’un digraphe. Il montre que l’atome d’un digraphe de Cayley qui contient l’unité est un sous-groupe et en déduit une courte preuve d’un résultat de Imrich. Il prouve que la connectivité d’un digraphe de Cayley ayant un ensemble minimal de générateurs est optimale généralisant ainsi un théorème de Godsil. Il construit une classe de digraphes de Cayley sur \({\mathbb{Z}}_ n\) ayant une connectivité optimale. Les digraphes étudiés sont finis.
Reviewer: G.Chaty

MSC:
05C20 Directed graphs (digraphs), tournaments
05C40 Connectivity
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Balinski, M.L.; Russakov, A., On the assignment polytope, SIAM rev., 16, 516-525, (1974) · Zbl 0269.90051
[2] Berge, C., Graphes et hypergraphes, (1970), Dunod Paris · Zbl 0213.25702
[3] Boesch, F.T.; Felger, A.P., A class of non vulnerable graphs, Networks, 2, 261-283, (1970)
[4] Brualdi, R.A.; Gibson, P.M., The convex polyhedron of doubly stochastic matrices. the graph of ω_n, J. combin. theory, ser. B, 22, 157-198, (1977)
[5] Chaty, G., On critically and minimally k vertex (arc) strongly connected digraphs, Proc. keszthely, 193-203, (1976) · Zbl 0386.05033
[6] Godsil, C.D., Connectivity of minimal Cayley graphs, Arch. math., 37, 437-476, (1981) · Zbl 0476.05049
[7] Halin, R., Graphentheorie II, (1981), Wiss. Buchges Darmstadt
[8] Hamidoune, Y.O., ()
[9] Y.O. Hamidoune, Quelques problèmes de connexité dans les Gaphes orientés, J. Combin. Theory, Ser. B
[10] Imrich, W., On the connectivity of Cayley graphs, J. combin. theory, ser B, 26, 323-326, (1979) · Zbl 0331.05114
[11] Mader, W., Eine eigenschaft der atome endlicher graphen, Arch. math., 22, 331-336, (1971) · Zbl 0214.51503
[12] Mader, W., Über den zusammen symmetricher graphen, Arch. math., 21, 331-336, (1970) · Zbl 0201.56804
[13] . Watkins, M.E, Connectivity of transitive graphs, J. combin. theory, 8, 23-29, (1970) · Zbl 0185.51702
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.