✦ LIBER ✦

Small cutsets in quasiminimal Cayley graphs

✍ Scribed by Y.O. Hamidoune; A.S. Lladó; O. Serra

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 586 KB
Volume: 159
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(95)00105-6

No coin nor oath required. For personal study only.

✦ Synopsis

We continue the recent study carried out by several authors on the cut sets in Cayley graphs with respect to quasiminimal generating sets. We improve the known results on these questions.

The application of our main theorem to symmetric Cayley graphs on minimal generating sets leads to the following result.

Let G be a group containing a minimal generating set M such that I MI ~> 4. Let S = M w M-~. Then one of the following conditions holds.

(i) s z=u 2andu 4=l,foralls,uEM (ii) For all (d + 1)-subsets A and B of G which are not of the form F(x)w {x} for any x e G, there exists d + 1 disjoint paths from A to B in Cay(G, S).

📜 SIMILAR VOLUMES

Matching cutsets in graphs

✍ Augustine M. Moshi 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 504 KB

Let G = ( Y E ) be an undirected graph. A subset F of E is a matching cutset of G if no two edges of Fare incident with the same point, and G-F has more components than G. ChGatal [2] proved that it is NP-complete to recognize graphs with a matching cutset even if the input is restricted to graphs w

Complete Rotations in Cayley Graphs

✍ Marie-Claude Heydemann; Nausica Marlin; Stéphane Pérennes 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 220 KB

As it is introduced by Bermond, Pérennes, and Kodate and by Fragopoulou and Akl, some Cayley graphs, including most popular models for interconnection networks, admit a special automorphism, called complete rotation. Such an automorphism is often used to derive algorithms or properties of the underl

Hamiltonian circuits in Cayley graphs

✍ Dragan Marušič 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 268 KB

Kernels in graphs with a clique-cutset

✍ Henry Jacob 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 138 KB

We consider graphs that have a clique-cutset, and we show that this property preserves the existence of a kernel in a certain sense. We consider finite directed graphs that do not have multiple arcs or loops, but there may be symmetric arcs between some pairs of vertices. Let G = (V, A) be a direct

Hamiltonian cycles in cayley color graph

Hamiltonian cycles in cayley color graphs

✍ Joseph B. Klerlein 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 165 KB 👁 1 views

## Abstract A group Γ is said to possess a hamiltonian generating set if there exists a minimal generating set Δ for Γ such that the Cayley color graph __D__~Δ~(Γ) is hamiltonian. It is shown that every finite abelian group has a hamiltonian generating set. Certain classes of nonabelian groups are

Disjoint clique cutsets in graphs withou

Disjoint clique cutsets in graphs without long holes

✍ Elaine M. Eschen; Chính T. Hoàng; Mark D. T. Petrick; R. Sritharan 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 182 KB

## Abstract A biclique cutset is a cutset that induces the disjoint union of two cliques. A hole is an induced cycle with at least five vertices. A graph is biclique separable if it has no holes and each induced subgraph that is not a clique contains a clique cutset or a biclique cutset. The class