✦ LIBER ✦

On the extraconnectivity of graphs

✍ Scribed by J. Fàbrega; M.A. Fiol

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 420 KB
Volume: 155
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(94)00369-t

No coin nor oath required. For personal study only.

✦ Synopsis

Given a simple connected graph G, let K(n) [2(n)] be the minimum cardinality of a set of vertices [edges], if any, whose deletion disconnects G and every remaining component has more than n vertices. For instance, the usual connectivity and the superconnectivity of G correspond to x(0) and ~c(1 ), respectively. This paper gives sufficient conditions, relating the diameter of G with its girth, to assure optimum values of these conditional connectivities.

📜 SIMILAR VOLUMES

Extraconnectivity of graphs with large g

Extraconnectivity of graphs with large girth

✍ J. Fàbrega; M.A. Fiol 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 547 KB

On the coverings of graphs

✍ F.R.K. Chung 📂 Article 📅 1980 🏛 Elsevier Science 🌐 English ⚖ 383 KB

On the hamiltonian path graph of a graph

✍ George R. T. Hendry 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 491 KB 👁 1 views

The hamiltonian path graph H(F) of a graph F is that graph having the same vertex set as F and in which two vertices u and u are adjacent if and only if F contains a hamiltonian u -u path. First, in response to a conjecture of Chartrand, Kapoor and Nordhaus, a characterization of nonhamiltonian grap

On the embedding of graphs into graphs w

On the embedding of graphs into graphs with few eigenvalues

✍ Vu, Van H. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 726 KB

A graph is called of type k if it is connected, regular, and has k distinct eigenvalues. For example graphs of type 2 are the complete graphs, while those of type 3 are the strongly regular graphs. We prove that for any positive integer n, every graph can be embedded in n cospectral, non-isomorphic

On the editing distance of graphs

✍ Maria Axenovich; André Kézdy; Ryan Martin 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 169 KB 👁 2 views

## Abstract An edge‐operation on a graph __G__ is defined to be either the deletion of an existing edge or the addition of a nonexisting edge. Given a family of graphs $\cal G$, the editing distance from __G__ to $\cal G$ is the smallest number of edge‐operations needed to modify __G__ into a graph

On the cycle-isomorphism of graphs

✍ Xingxing Yu 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 336 KB

## Abstract This paper considers conditions ensuring that cycle‐isomorphic graphs are isomorphic. Graphs of connectivity ⩾ 2 that have no loops were studied in [2] and [4]. Here we characterize all graphs __G__ of connectivity 1 such that every graph that is cycle‐isomorphic to __G__ is also isomor