✦ LIBER ✦

On local connectivity of graphs

✍ Scribed by Lutz Volkmann

Publisher: Elsevier Science
Year: 2008
Tongue: English
Weight: 151 KB
Volume: 21
Category: Article
ISSN: 0893-9659
DOI: 10.1016/j.aml.2006.12.014

No coin nor oath required. For personal study only.

✦ Synopsis

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

} 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 locally connected when

for all pairs u and v of vertices in G. In 1993, Topp and Volkmann [J. Topp, L. Volkmann, Sufficient conditions for equality of connectivity and minimum degree of a graph, J. Graph Theory 17 (1993) 695-700] proved that a p-partite graph 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 locally connected.

📜 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

On the hamiltonicity of line graphs of l

On the hamiltonicity of line graphs of locally finite, 6-edge-connected graphs

✍ Richard C. Brewster; Daryl Funk 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 124 KB

## Abstract The topological approach to the study of infinite graphs of Diestel and KÜhn has enabled several results on Hamilton cycles in finite graphs to be extended to locally finite graphs. We consider the result that the line graph of a finite 4‐edge‐connected graph is hamiltonian. We prove a

On the minimum local-vertex-connectivity

On the minimum local-vertex-connectivity augmentation in graphs

✍ Hiroshi Nagamochi; Toshimasa Ishii 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 179 KB

Given a graph G and target values r(u; v) prescribed for each pair of vertices u and v, we consider the problem of augmenting G by a smallest set F of new edges such that the resulting graph G+F has at least r(u; v) internally disjoint paths between each pair of vertices u and v. We show that the pr

On locally k-critically n-connected grap

On locally k-critically n-connected graphs

✍ Jianji Su 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 479 KB

Su, J., On locally k-critically n-connected graphs, Discrete Mathematics 120 (1993) 183-190. Let 0 # W'g V(G). The graph G is called a W-locally k-critically n-connected graph or simply a W-locally (n, k)-graph, if for all V'G W with 1 V'I 6 k and each fragment F of G we have that K(G-V')=n-1 V' and

Graphs with prescribed local connectivit

Graphs with prescribed local connectivities

✍ Donald W. Vanderjagt 📂 Article 📅 1974 🏛 Elsevier Science 🌐 English ⚖ 537 KB

Local connectivity of a random graph

✍ P. Erdös; E. M. Palmer; R. W. Robinson 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 255 KB

## Abstract A graph is locally connected if for each vertex ν of degree __≧2__, the subgraph induced by the vertices adjacent to ν is connected. In this paper we establish a sharp threshold function for local connectivity. Specifically, if the probability of an edge of a labeled graph of order __n_