Displaying similar documents to “Some results concerning the ends of minimal cuts of simple graphs”

A note on minimally 3-connected graphs

Víctor Neumann-Lara, Eduardo Rivera-Campo, Jorge Urrutia (2004)

Discussiones Mathematicae Graph Theory

Similarity:

If G is a minimally 3-connected graph and C is a double cover of the set of edges of G by irreducible walks, then |E(G)| ≥ 2| C| - 2.

A simple linear algorithm for the connected domination problem in circular-arc graphs

Ruo-Wei Hung, Maw-Shang Chang (2004)

Discussiones Mathematicae Graph Theory

Similarity:

A connected dominating set of a graph G = (V,E) is a subset of vertices CD ⊆ V such that every vertex not in CD is adjacent to at least one vertex in CD, and the subgraph induced by CD is connected. We show that, given an arc family F with endpoints sorted, a minimum-cardinality connected dominating set of the circular-arc graph constructed from F can be computed in O(|F|) time.

Locally connected exceptional minimal sets of surface homeomorphisms

Andrzej Biś, Hiromichi Nakayama, Pawel Walczak (2004)

Annales de l’institut Fourier

Similarity:

We deal with locally connected exceptional minimal sets of surface homeomorphisms. If the surface is different from the torus, such a minimal set is either finite or a finite disjoint union of simple closed curves. On the torus, such a set can admit also a structure similar to that of the Sierpiński curve.

Characterizing Atoms that Result from Decomposition by Clique Separators

Terry A. McKee (2017)

Discussiones Mathematicae Graph Theory

Similarity:

A graph is defined to be an atom if no minimal vertex separator induces a complete subgraph; thus, atoms are the graphs that are immune to clique separator decomposition. Atoms are characterized here in two ways: first using generalized vertex elimination schemes, and then as generalizations of 2-connected unichord-free graphs (the graphs in which every minimal vertex separator induces an edgeless subgraph).

Graphs without induced P₅ and C₅

Gabor Bacsó, Zsolt Tuza (2004)

Discussiones Mathematicae Graph Theory

Similarity:

Zverovich [Discuss. Math. Graph Theory 23 (2003), 159-162.] has proved that the domination number and connected domination number are equal on all connected graphs without induced P₅ and C₅. Here we show (with an independent proof) that the following stronger result is also valid: Every P₅-free and C₅-free connected graph contains a minimum-size dominating set that induces a complete subgraph.