On local connectivity of graphs with given clique number

✍ Scribed by Andreas Holtkamp; Lutz Volkmann

• Publisher: John Wiley and Sons
• Year: 2009
• Tongue: English
• Weight: 72 KB
• Volume: 63
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20419

✦ Synopsis

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 defined as κ(G)=min{κ(u, v)|u, v∈V(G)}. Clearly, κ(u, v)⩽min{d(u),
d(v)} for all pairs u and v of vertices in G. Let δ(G) be the minimum degree of G. We call a graph G maximally connected when κ(G)=δ(G) and maximally local connected
when

for all pairs u and v of distinct vertices in G.

In 2006, Hellwig and Volkmann (J Graph Theory 52 (2006), 7–14) proved that a connected graph G with given clique number ω(G)⩽p of order n(G) is maximally connected when
As an extension of this result, we will show in this work that these conditions even guarantee that G is maximally local connected. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 192–197, 2010