✦ LIBER ✦

On the honesty of graph complements

✍ Scribed by K.S. Bagga; L.W. Beineke; M.J. Lipman; R.E. Pippert

Publisher: Elsevier Science
Year: 1993
Tongue: English
Weight: 342 KB
Volume: 122
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(93)90282-x

No coin nor oath required. For personal study only.

✦ Synopsis

A graph is called honest if its edge-integrity equals its order. It is shown in this paper that except for the path of length 3, every graph that is not honest has an honest complemenk. This result is extended to complements of products and applied to the Nordhaus-Gaddum theory for edgeintegrity.

📜 SIMILAR VOLUMES

On the edge-integrity of some graphs and

On the edge-integrity of some graphs and their complements

✍ R. Laskar; S. Stuecle; B. Piazza 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 483 KB

In this paper the authors study the edge-integrity of graphs. Edge-integrity is a very useful measure of the vulnerability of a network, in particular a communication network, to disruption through the deletion of edges. A number of problems are examined, including some Nordhaus-Gaddum type results.

On graphs with complete bipartite star c

On graphs with complete bipartite star complements

✍ P.S. Jackson; P. Rowlinson 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 119 KB

Let µ be an eigenvalue of the graph G with multiplicity m. A star complement for µ in G is an induced subgraph G -X such that |X| = m and µ is not an eigenvalue of G -X. Some general observations concerning graphs with the complete bipartite graph K r,s (r + s > 2) as a star complement are followed

On completely positive graphs and their

On completely positive graphs and their complements

✍ Felix Goldberg 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 81 KB

In this paper we establish two results concerning completely positive graphs and their complements: (1) the complement of a completely positive graph on n 9 vertices is not completely positive; (2) the spectral radius of the adjacency matrix of a completely positive graph on n 6 vertices is at most

On the graph complement conjecture for m

On the graph complement conjecture for minimum semidefinite rank

✍ Lon H. Mitchell 📂 Article 📅 2011 🏛 Elsevier Science 🌐 English ⚖ 158 KB

Hyperbolicity and complement of graphs

✍ Sergio Bermudo; José M. Rodríguez; José M. Sigarreta; Eva Tourís 📂 Article 📅 2011 🏛 Elsevier Science 🌐 English ⚖ 280 KB

If X is a geodesic metric space and x 1 , x 2 , x 3 ∈ X , a geodesic triangle T = {x 1 , x 2 , x 3 } is the union of the three geodesics [x 1 x 2 ], [x 2 x 3 ] and [x 3 x 1 ] in X . The space X is δ-hyperbolic (in the Gromov sense) if any side of T is contained in a δ-neighborhood of the union of th

Disconnected Complements of Steinhaus gr

Disconnected Complements of Steinhaus graphs

✍ Wayne M. Dymàček; Matthew Koerlin; Jean-Guy Speton; Tom Whaley; Jennifer Yanulav 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 548 KB