𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the edge-integrity of some graphs and their complements

✍ Scribed by R. Laskar; S. Stuecle; B. Piazza

Publisher
Elsevier Science
Year
1993
Tongue
English
Weight
483 KB
Volume
122
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

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. Honest graphs, i.e. those which have the maximum possible edge-integrity, are also investigated. A number of interesting open problems are also posed.

πŸ“œ SIMILAR VOLUMES

Some undecidable problems involving the
Some undecidable problems involving the edge-coloring and vertex-coloring of graphs
✍ Stefan A. Burr πŸ“‚ Article πŸ“… 1984 πŸ› Elsevier Science 🌐 English βš– 477 KB

Certain problems involving the coloring the edges or vertices of infinite graphs are shown to be undecidable. In particular, let G and H be finite 3-connected graphs, or triangles. Then a doubly-periodic infinite graph F is constructed such that the following problem is undecidable: For a coloring o

On the two-edge-colorings of perfect gra
On the two-edge-colorings of perfect graphs
✍ ChΓ­nh T. HoΓ ng πŸ“‚ Article πŸ“… 1995 πŸ› John Wiley and Sons 🌐 English βš– 409 KB πŸ‘ 1 views

## Abstract We investigate the conjecture that a graph is perfect if it admits a two‐edge‐coloring such that two edges receive different colors if they are the nonincident edges of a __P__~4~ (chordless path with four vertices). Partial results on this conjecture are given in this paper. Β© 1995 Joh

Some results on characterizing the edges
Some results on characterizing the edges of connected graphs with a given domination number
✍ Laura A. Sanchis πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 821 KB

A dominatin# set for a graph G = (V, E) is a subset of vertices V' c\_ V such that for all v β€’ V-V' there exists some uβ€’ V' for which {v,u} β€’E. The domination number of G is the size of its smallest dominating set(s). For a given graph G with minimum size dominating set D, let mz(G, D) denote the nu

On the hamiltonicity of line graphs of l
On the hamiltonicity of line graphs of locally finite, 6-edge-connected graphs
✍ Richard C. Brewster; Daryl Funk πŸ“‚ Article πŸ“… 2011 πŸ› John Wiley and Sons 🌐 English βš– 124 KB

## Abstract The topological approach to the study of infinite graphs of Diestel and KÜhn has enabled several results on Hamilton cycles in finite graphs to be extended to locally finite graphs. We consider the result that the line graph of a finite 4‐edge‐connected graph is hamiltonian. We prove a

On the Edge Connectivity, Hamiltonicity,
On the Edge Connectivity, Hamiltonicity, and Toughness of Vertex-Transitive Graphs
✍ Jan van den Heuvel; Bill Jackson πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 191 KB

Let G be a connected k-regular vertex-transitive graph on n vertices. For S V(G) let d(S) denote the number of edges between S and V(G)"S. We extend results of Mader and Tindell by showing that if d(S)< 2 9 (k+1) 2 for some S V(G) with 1 3 (k+1) |S| 1 2 n, then G has a factor F such that GΓ‚E(F ) is