✦ LIBER ✦

Graphs with given connectivity properties

✍ Scribed by Lawrencenko, Serge; Luo, Qiang

Publisher: John Wiley and Sons
Year: 1997
Tongue: English
Weight: 98 KB
Volume: 30
Category: Article
ISSN: 0028-3045
DOI: 10.1002/(sici)1097-0037(199712)30:4<255::aid-net3>3.0.co;2-i

No coin nor oath required. For personal study only.

✦ Synopsis

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 connectivity, the more reliable the network). Two nodes are called reliably connected if they are joined by a reliable path, i.e., a path whose internal nodes (if any) are all redundant. For a given n, we construct a communication network on n nodes having a given value k of connectivity (reliability condition) and as few edges as possible (optimization condition) and in which any pair of nodes, with one exceptional node, are reliably connected (reliable connectedness condition). We also studied the associated-with-G ''strong redundancy graph'' and a sequence of ''weak redundancy graphs,'' quotient graphs which display decompositions of G into connected subgraphs in accordance with the contributions of the nodes to the connectivity k(G).

📜 SIMILAR VOLUMES

On connectivity in graphs with given cli

On connectivity in graphs with given clique number

✍ Angelika Hellwig; Lutz Volkmann 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 82 KB 👁 1 views

## 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 f

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 prescribed connectivity and

Graphs with prescribed connectivity and line graph connectivity

✍ Douglas Bauer; Ralph Tindell 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 118 KB

## Abstract Chartrand and Stewart have shown that the line graph of an __n__‐connected graph is itself __n__‐connected. This paper shows that for every pair of integers __m__ > __n__ > 1 there is a graph of point connectivity __n__ whose line graph has point connectivity __m__. The corresponding qu

Graphs with given odd sets

✍ Chen, Guantao; Schelp, Richard H.; ?olt�s, ?ubom�r 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 123 KB

Given a graph G, its odd set is a set of all integers k such that G has odd number of vertices of degree k. We show that if two graphs G and H of the same order have the same odd sets then they can be obtained from each other by succesive application of the following two operations: • add or remove

Graphs with given group and given consta

Graphs with given group and given constant link

✍ Walter Vogler 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 228 KB

## Abstract __A__ graph __L__ is called a link graph if there is a graph __G__ such that for each vertex of __G__ its neighbors induce a subgraph isomorphic to __L.__ Such a G is said to have constant link __.__L Sabidussi proved that for any finite group F and any __n__ ⩾ 3 there are infinitely ma

Regular graphs with given girth pair

✍ Frank Harary; Peter Kovács 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 453 KB 👁 1 views

## Abstract The girth pair of a graph gives the length of a shortest odd and a shortest even cycle. The existence of regular graphs with given degree and girth pair is proved and simple bounds for their smallest order are developed. Several infinite classes of such graphs are constructed and it is