The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

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: