𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On connectivity in graphs with given clique number

✍ Scribed by Angelika Hellwig; Lutz Volkmann

Publisher
John Wiley and Sons
Year
2006
Tongue
English
Weight
82 KB
Volume
52
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We consider finite, undirected, and simple graphs G of order n(G) and minimum degree Ξ΄(G). The connectivity ΞΊ(G) for a connected graph G is defined as the minimum cardinality over all vertex‐cuts.

If ΞΊ(G) < δ(G), then Topp and Volkmann 7 showed in 1993 for p‐partite graphs G that

As a simple consequence, Topp and Volkmann obtained for p‐partite graphs G the identity ΞΊ(G) = δ(G), if

In this article, we will show that these results remain true for graphs G with Ο‰(G) ≀ p, where Ο‰(G) denotes the clique number of G. Since each p‐partite graph G satisfies Ο‰(G) ≀ p, this generalizes the results of Topp and Volkmann. Β© 2006 Wiley Periodicals, Inc. J Graph Theory 52: 7–14, 2006

πŸ“œ SIMILAR VOLUMES

On local connectivity of graphs with giv
On local connectivity of graphs with given clique number
✍ Andreas Holtkamp; Lutz Volkmann πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 72 KB

## Abstract For a vertex __v__ of a graph __G__, we denote by __d__(__v__) the __degree__ of __v__. The __local connectivity__ ΞΊ(__u, v__) of two vertices __u__ and __v__ in a graph __G__ is the maximum number of internally disjoint __u__ –__v__ paths in __G__, and the __connectivity__ of __G__ is

Graphs with given connectivity propertie
Graphs with given connectivity properties
✍ Lawrencenko, Serge; Luo, Qiang πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 98 KB

A node of a graph G, thought of as representing a communication network, is said to be redundant provided that its removal does not diminish the connectivity. In constructing networks, we require reliable connectedness in addition to the usual requirement of reliability (i.e., the higher the connect

Dense graphs with small clique number
Dense graphs with small clique number
✍ Wayne Goddard; Jeremy Lyle πŸ“‚ Article πŸ“… 2010 πŸ› John Wiley and Sons 🌐 English βš– 121 KB
On the Ramsey number of trees versus gra
On the Ramsey number of trees versus graphs with large clique number
✍ Ronald J. Gould; Michael S. Jacobson πŸ“‚ Article πŸ“… 1983 πŸ› John Wiley and Sons 🌐 English βš– 335 KB

Chvatal established that r(T,, K,,) = (m -1 ) ( n -1 ) + 1, where T, , , is an arbitrary tree of order m and K, is the complete graph of order n. This result was extended by Chartrand, Gould, and Polimeni who showed K, could be replaced by a graph with clique number n and order n + 5 provided n 2 3