On the edge-integrity of some graphs and their complements
type: Item
instance of: scholarly article
title: On the edge-integrity of some graphs and their complements
zbMATH Open document ID: 0796.05059
DOI: 10.1016/0012-365X(93)90299-9
published in: Discrete Mathematics
publication date: 1994-09-15T00:00:00Z
review text: The edge integrity of a graph \(G\) is defined as \(I'(G)=\min_{S \subseteq E(G)} \{| S |+m (G-S)\}\) where \(m(G-S)\) denotes the order of a largest component of \(G-S\). A graph \(G\) is called honest if \(I'(G)=p\) where \(p\) is the order of \(G\). Some Nordhaus-Gaddum type results are obtained after which the authors ask when \(I'(G) + I' (\overline G) = 2p\). After asking for which graphs \(G\) do both \(G\) and its complement have diameter 2, the authors study graphs with diameter 2. They then show (Theorem 8), for example, that if graphs \(G\) and \(H\) each have order at least 3 then \(\overline {G \times H}\) is honest. One of the closing questions asks for the edge integrity of self-complementary graphs.
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 500641
zbMATH Keywords: honest graph
zbMATH Keywords: integrity
zbMATH Keywords: Nordhaus-Gaddum type results
author: Renu C. Laskar
author: Sam Stueckle
author: B. L. Piazza
reviewed by: R. C. Entringer
MaRDI profile type: Publication
cites work: Q4873690
cites work: A classification scheme for vulnerability and reliability parameters of graphs
cites work: Q3815334
cites work: Q3835470
cites work: On the honesty of graph complements
cites work: Q3781769
cites work: Q3789603
cites work: Q3158579
cites work: Q3775581
cites work: Q3032280
cites work: The complexity of comparability graph recognition and coloring
cites work: Q3981352
cites work: Q4711931
full work available at URL: 0012-365x(93)90299-9
OpenAlex ID: W1999103501
description: scientific article; zbMATH DE number 500641