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

Ruo-Wei Hung; Maw-Shang Chang

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 \subseteq 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...

An efficient $g$ -centroid location algorithm for cographs.

Prakash, V. (2005)

International Journal of Mathematics and Mathematical Sciences

Similarity:

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...