✦ LIBER ✦

Reduced graphs of diameter two

✍ Scribed by Hong-Jian Lai

Publisher: John Wiley and Sons
Year: 1990
Tongue: English
Weight: 444 KB
Volume: 14
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190140109

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A graph H is collapsible if for every subset X ⊆ V(H), H has a spanning connected subgraph whose set of odd‐degree vertices is X. In any graph G there is a unique collection of maximal collapsible subgraphs, and when all of them are contracted, the resulting contraction of G is a reduced graph. Interest in reduced graphs arises from the fact [4] that a graph G has a spanning closed trail if and only if its corresponding reduced graph has a spanning closed trail. The concept can also be applied to study hamiltonian line graphs [11] or double cycle covers [8]. In this article, we characterize the reduced graphs of diameter two. As applications, we obtain prior results in [12] and [14], and show that every 2‐edge‐connected graph with diameter at most two either admits a double cycle cover with three even subgraphs or is isomorphic to the Petersen graph.

📜 SIMILAR VOLUMES

Diameter of the conjunction of two finit

Diameter of the conjunction of two finite graphs

✍ Roger H. Lamprey 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 227 KB

Pebbling in diameter two graphs and prod

Pebbling in diameter two graphs and products of paths

✍ Clarke, T. A.; Hochberg, R. A.; Hurlbert, G. H. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 151 KB 👁 1 views

Results regarding the pebbling number of various graphs are presented. We say a graph is of Class 0 if its pebbling number equals the number of its vertices. For diameter d we conjecture that every graph of sufficient connectivity is of Class 0. We verify the conjecture for d = 2 by characterizing t

Maximal and Minimal Vertex-Critical Grap

Maximal and Minimal Vertex-Critical Graphs of Diameter Two

✍ Jing Huang; Anders Yeo 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 446 KB

A graph is vertex-critical if deleting any vertex increases its diameter. We construct, for each & 5 except &=6, a vertex-critical graph of diameter two on & vertices with at least , where c 2 is some constant. We also construct, for each & 5 except &=6, a vertex-critical graph of diameter two on &

On diameter of permutation graphs

✍ Gu, Weizhen 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 109 KB 👁 2 views

Let G be a connected graph with n vertices. Let a be a permutation in S n . The a-generalized graph over G, denoted by P a (G), consists of two disjoint, identical copies of G along with edges £a(£). In this paper, we investigated the relation between diameter of P a (G) and diameter of G for any pe

Diameters of iterated clique graphs of c

Diameters of iterated clique graphs of chordal graphs

✍ Bor-Liang Chen; Ko-Wei Lih 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 272 KB

## Abstract The clique graph __K__(__G__) of a graph is the intersection graph of maximal cliques of __G.__ The iterated clique graph __K__^__n__^(__G__) is inductively defined as __K__(K^n−1^(__G__)) and __K__^1^(__G__) = __K__(__G__). Let the diameter diam(__G__) be the greatest distance between

2-diameter of de Bruijn graphs

✍ Li, Qiao; Sotteau, Dominique; Xu, Junming 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 589 KB

This paper shows that in the undirected binary de Bruijn graph of dimension n . UB(n), which has diameter n , there exist at least two internally vertex disjoint paths of length at most n between any two vertices. In other words, the 2-diameter of U B ( n ) is equal to its diameter n .