✦ LIBER ✦

More powerful closure operations on graphs

✍ Scribed by Yong-jin Zhu; Feng Tian; Xiao-tie Deng

Publisher: Elsevier Science
Year: 1991
Tongue: English
Weight: 1017 KB
Volume: 87
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(91)90049-8

No coin nor oath required. For personal study only.

✦ Synopsis

Zhu, Y.-J., F. Tian and X.-T. Deng, More powerful closure operations on graphs, Discrete Mathematics 87 (1991) 197-214. Bondy and Chvatal have observed the following result: G = (V, E) is a simple graph of order n. If uu $ E and d(u) + d(u) 2 n, then G is Hamiltonian iff G + uu is Hamiltonian. Thus, we can obtain a graph C,(G), named the n-closure of G, from G by successively joining pairs of non-adjacent vertices whose degree sum is at least n. Therefore, G is Hamiltonian if C,(G) is Hamiltonian. Moreover, Bondy and Chvatal (21 generalized this idea to several properties on G. In the paper, we present some more powerful closure operations that extend the idea of Bondy and Chvatal.

📜 SIMILAR VOLUMES

Operations on fuzzy graphs

✍ John N. Mordeson; Peng Chang-Shyh 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 651 KB

NEPS operations on cordial graphs

✍ Walter W. Kirchherr 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 557 KB

Some applications of the closure operati

Some applications of the closure operation in graph analysis

✍ V.V. Martynyuk 📂 Article 📅 1971 🏛 Elsevier Science ⚖ 309 KB

Closure of Boolean operations on geometr

Closure of Boolean operations on geometric entities

✍ R.B. Tilove; A.A.G. Requicha 📂 Article 📅 1980 🏛 Elsevier Science 🌐 English ⚖ 811 KB

Boolean operations akin to set intersection, union, and difference play an important role in CAD/CAM. Geometric entities of practical interest (e.g. polygons or polyhedra) are not algebraically closed under the conventional set operators, and therefore algorithms cannot implement conventional set op

The bandwidth problem and operations on

The bandwidth problem and operations on graphs

✍ J Chvatalova; J Opatrny 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 479 KB

For a given graph G and vertices u, v in G let ,,,~ ~(.,~) G(-,,o) G~, o) denote the graph Gm ~ Va , ~s :, obtained from G by merging vertices u, v, adding edge (u, v), subdividing edge (u, v), contracting edge (u, v) of G, respectively. We give upper and lower bounds for the bandwidth of ~'~ ~(~'~)

On many-sorted algebraic closure operato

On many-sorted algebraic closure operators

✍ Juan Climent Vidal; Juan Soliveres Tur 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 96 KB

## Abstract A theorem of Birkhoff‐Frink asserts that every algebraic closure operator on an ordinary set arises, from some algebraic structure on the set, as the corresponding generated subalgebra operator. However, for many‐sorted sets, i.e., indexed families of sets, such a theorem is not longer