Displaying similar documents to “A simple linear algorithm for the connected domination problem in circular-arc graphs”

On the doubly connected domination number of a graph

Joanna Cyman, Magdalena Lemańska, Joanna Raczek (2006)

Open Mathematics

Similarity:

For a given connected graph G = (V, E), a set D ⊆ V ( G ) is a doubly connected dominating set if it is dominating and both 〈D〉 and 〈V (G)-D〉 are connected. The cardinality of the minimum doubly connected dominating set in G is the doubly connected domination number. We investigate several properties of doubly connected dominating sets and give some bounds on the doubly connected domination number.

The vertex monophonic number of a graph

A.P. Santhakumaran, P. Titus (2012)

Discussiones Mathematicae Graph Theory

Similarity:

For a connected graph G of order p ≥ 2 and a vertex x of G, a set S ⊆ V(G) is an x-monophonic set of G if each vertex v ∈ V(G) lies on an x -y monophonic path for some element y in S. The minimum cardinality of an x-monophonic set of G is defined as the x-monophonic number of G, denoted by mₓ(G). An x-monophonic set of cardinality mₓ(G) is called a mₓ-set of G. We determine bounds for it and characterize graphs which realize these bounds. A connected graph of order p with vertex monophonic...

Connected domatic number in planar graphs

Bert L. Hartnell, Douglas F. Rall (2001)

Czechoslovak Mathematical Journal

Similarity:

A dominating set in a graph G is a connected dominating set of G if it induces a connected subgraph of G . The connected domatic number of G is the maximum number of pairwise disjoint, connected dominating sets in V ( G ) . We establish a sharp lower bound on the number of edges in a connected graph with a given order and given connected domatic number. We also show that a planar graph has connected domatic number at most 4 and give a characterization of planar graphs having connected domatic...

Planar Graphs

Hassler Whitney (1933)

Fundamenta Mathematicae

Similarity: