𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Conditional diameter saturated graphs

✍ Scribed by C. Balbuena; P. García-Vázquez; X. Marcote; J.C. Valenzuela

Publisher
John Wiley and Sons
Year
2008
Tongue
English
Weight
115 KB
Volume
52
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

The conditional diameter D~𝒫~(G) of a connected graph G is a measure of the maximum distance between two subsets of vertices satisfying a given property 𝒫 of interest. For any given integer k ≥ 1, a connected graph G is said to be conditional diameter k‐saturated if D~𝒫~(G) ≥ k and there does not exist any other connected graph G′ with order ∣V(G′)∣ = ∣V(G)∣, size ∣E(G′)∣ > ∣E(G)∣, and conditional diameter D~𝒫~(G′) ≥ k. In this article, we obtain such conditional diameter saturated graphs for a number of properties 𝒫, generalizing the results obtained in (Ore, J Combin Theory 5(1968), 75–81) for the (standard) diameter D(G). © 2008 Wiley Periodicals, Inc. NETWORKS, 2008

📜 SIMILAR VOLUMES

On the superconnectivity and the conditi
On the superconnectivity and the conditional diameter of graphs and digraphs
✍ Carmona, A.; F�brega, J. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 142 KB 👁 2 views

It has been proved that if the diameter D of a digraph G satisfies D Յ 2ᐉ Ϫ 2, where ᐉ is a parameter which can be thought of as a generalization of the girth of a graph, then G is superconnected. Analogously, if D Յ 2ᐉ Ϫ 1, then G is edge-superconnected. In this paper, we studied some similar condi

On the connectivity and the conditional
On the connectivity and the conditional diameter of graphs and digraphs
✍ Balbuena, C.; Carmona, A.; F�brega, J.; Fiol, M. A. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 771 KB

Recently, it was proved that if the diameter D of a graph G is small enough in comparison with its girth, then G is maximally connected and that a similar result also holds for digraphs. More precisely, if the diameter D of a digraph G satisfies D 5 21 -1, then G has maximum connectivity ( K = 6 ) .

Conditional Fault Diameter of Star Graph
Conditional Fault Diameter of Star Graph Networks
✍ Yordan Rouskov; Shahram Latifi; Pradip K. Srimani 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 300 KB

It is well known that star graphs are strongly resilient like the n cubes in the sense that they are optimally fault tolerant and the fault diameter is increased only by one in the presence of maximum number of allowable faults. We investigate star graphs under the conditions of forbidden faulty set

Detour-saturated graphs
Detour-saturated graphs
✍ Lowell W. Beineke; J. E. Dunbar; M. Frick 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 160 KB

## Abstract A graph is said to be detour‐saturated if the addition of any edge results in an increased greatest path length. In this paper, we add to the relatively small amount that is known about detour‐saturated graphs. Our main result is a determination of all connected detour‐saturated graphs