The forcing dimension of a graph

Gary Chartrand; Ping Zhang

Displaying similar documents to “The forcing dimension of a graph”

Resolving domination in graphs

Robert C. Brigham, Gary Chartrand, Ronald D. Dutton, Ping Zhang (2003)

Mathematica Bohemica

Similarity:

For an ordered set $W = {w_{1}, w_{2}, \dots, w_{k}}$ of vertices and a vertex $v$ in a connected graph $G$ , the (metric) representation of $v$ with respect to $W$ is the $k$ -vector $r (v | W) = (d (v, w_{1}), d (v, w_{2}), \dots, d (v, w_{k}))$ , where $d (x, y)$ represents the distance between the vertices $x$ and $y$ . The set $W$ is a resolving set for $G$ if distinct vertices of $G$ have distinct representations with respect to $W$ . A resolving set of minimum cardinality is called a minimum resolving set or a basis and the cardinality of a basis for $G$ is its dimension $dim G$ . A set $S$ of vertices in $G$ is a dominating...

Connected resolvability of graphs

Varaporn Saenpholphat, Ping Zhang (2003)

Czechoslovak Mathematical Journal

Similarity:

For an ordered set $W = {w_{1}, w_{2}, \dots, w_{k}}$ of vertices and a vertex $v$ in a connected graph $G$ , the representation of $v$ with respect to $W$ is the $k$ -vector $r (v | W)$ = ( $d (v, w_{1})$ , $d (v, w_{2}), \dots, d (v, w_{k}))$ , where $d (x, y)$ represents the distance between the vertices $x$ and $y$ . The set $W$ is a resolving set for $G$ if distinct vertices of $G$ have distinct representations with respect to $W$ . A resolving set for $G$ containing a minimum number of vertices is a basis for $G$ . The dimension $dim (G)$ is the number of vertices in a basis for $G$ . A resolving set $W$ of $G$ is connected...

A note on periodicity of the 2-distance operator

Bohdan Zelinka (2000)

Discussiones Mathematicae Graph Theory

Similarity:

The paper solves one problem by E. Prisner concerning the 2-distance operator T₂. This is an operator on the class $C_{f}$ of all finite undirected graphs. If G is a graph from $C_{f}$ , then T₂(G) is the graph with the same vertex set as G in which two vertices are adjacent if and only if their distance in G is 2. E. Prisner asks whether the periodicity ≥ 3 is possible for T₂. In this paper an affirmative answer is given. A result concerning the periodicity 2 is added.

Distance in stratified graphs

Gary Chartrand, Lisa Hansen, Reza Rashidi, Naveed Sherwani (2000)

Czechoslovak Mathematical Journal

Similarity:

A graph $G$ is stratified if its vertex set is partitioned into classes, called strata. If there are $k$ strata, then $G$ is $k$ -stratified. These graphs were introduced to study problems in VLSI design. The strata in a stratified graph are also referred to as color classes. For a color $X$ in a stratified graph $G$ , the $X$ -eccentricity $e_{X} (v)$ of a vertex $v$ of $G$ is the distance between $v$ and an $X$ -colored vertex furthest from $v$ . The minimum $X$ -eccentricity among the vertices of $G$ is the $X$ -radius ${r a d}_{X} G$ of $G$ ...

Signed total domination number of a graph

Bohdan Zelinka (2001)

Czechoslovak Mathematical Journal

Similarity:

The signed total domination number of a graph is a certain variant of the domination number. If $v$ is a vertex of a graph $G$ , then $N (v)$ is its oper neighbourhood, i.e. the set of all vertices adjacent to $v$ in $G$ . A mapping $f : V (G) \to {- 1, 1}$ , where $V (G)$ is the vertex set of $G$ , is called a signed total dominating function (STDF) on $G$ , if $\sum_{x \in N (v)} f (x) \geq 1$ for each $v \in V (G)$ . The minimum of values $\sum_{x \in V (G)} f (x)$ , taken over all STDF’s of $G$ , is called the signed total domination number of $G$ and denoted by $γ_{s t} (G)$ . A theorem stating lower bounds for $γ_{s t} (G)$ is...