✦ LIBER ✦

Detour-saturated graphs

✍ Scribed by Lowell W. Beineke; J. E. Dunbar; M. Frick

Publisher: John Wiley and Sons
Year: 2005
Tongue: English
Weight: 160 KB
Volume: 49
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20069

No coin nor oath required. For personal study only.

✦ Synopsis

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 with exactly one cycle. (The family of detour‐saturated trees was found by Kászonyi and Tuza 7.) We also show that the smallest detour‐saturated graph of girth 5 is the graph obtainable from the Petersen graph by splitting one of its vertices into three, each of degree 1. © 2005 Wiley Periodicals, Inc. J Graph Theory

📜 SIMILAR VOLUMES

Edge-colored saturated graphs

✍ D. Hanson; B. Toft 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 266 KB

Conditional diameter saturated graphs

✍ C. Balbuena; P. García-Vázquez; X. Marcote; J.C. Valenzuela 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 115 KB

## 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__‐s

Minimum C5-saturated graphs

✍ Ya-Chen Chen 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 208 KB

## Abstract A graph is __C__~5~‐saturated if it has no five‐cycle as a subgraph, but does contain a __C__~5~ after the addition of any new edge. We prove that the minimum number of edges in a __C__~5~ ‐saturated graph on __n__≥11 vertices is __sat__(__n, C__~5~)=⌈10(__n__−1)/7⌉−1 if __n__∈__N__~0~=

m_Path Cover Saturated Graphs

✍ Aneta Dudek; Gyula Y. Katona; A.Pawel Wojda 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 258 KB

Ramsey unsaturated and saturated graphs

✍ P. Balister; J. Lehel; R.H. Schelp 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 119 KB

## Abstract A graph is __Ramsey unsaturated__ if there exists a proper supergraph of the same order with the same Ramsey number, and __Ramsey saturated__ otherwise. We present some conjectures and results concerning both Ramsey saturated and unsaturated graphs. In particular, we show that cycles __

Asymptotic results on saturated graphs

✍ Miroslaw Truszczynski; Zsolt Tuza 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 449 KB

Truszczynski, M. and Z. Tuza, Asymptotic results on saturated graphs, Discrete Mathematics 87 (1991) 309-314 Let F be a given graph. A graph G is called F-saturated if F & G and F c G + e for every edge e $ E(G), e E V(G). Denote by sat(n, F) the minimum number of edges in an F-saturated graph on n