Premium
The complete closure of a graph
Author(s) -
Faudree Ralph,
Favaron Odile,
Flandrin Evelyne,
Li Hao
Publication year - 1993
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190170406
Subject(s) - combinatorics , mathematics , closure (psychology) , graph , integer (computer science) , discrete mathematics , complete graph , order (exchange) , computer science , finance , economics , market economy , programming language
We define the complete closure number cc( G ) of a graph G of order n as the greatest integer k ≤ 2n − 3 such that the k th Bondy‐Chvátal closure Cl k ( G ) is complete, and give some necessary or sufficient conditions for a graph to have cc( G ) = k . Similarly, the complete stability cs( P ) of a property P defined on all the graphs of order n is the smallest integer k such that if Cl k ( G ) is complete then G satisfies P. For some properties P , we compare cs( P ) with the classical stability s( P ) of P and show that cs( P ) may be far smaller than s( P ). © 1993 John Wiley & Sons, Inc.