# The forcing dimension of a graph

Mathematica Bohemica (2001)

- Volume: 126, Issue: 4, page 711-720
- ISSN: 0862-7959

## Access Full Article

top## Abstract

top## How to cite

topChartrand, Gary, and Zhang, Ping. "The forcing dimension of a graph." Mathematica Bohemica 126.4 (2001): 711-720. <http://eudml.org/doc/248877>.

@article{Chartrand2001,

abstract = {For an ordered set $W=\lbrace w_1, w_2, \cdots , w_k\rbrace $ 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),\cdots , 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. A resolving set of minimum cardinality is a basis for $G$ and the number of vertices in a basis is its (metric) dimension $\dim (G)$. For a basis $W$ of $G$, a subset $S$ of $W$ is called a forcing subset of $W$ if $W$ is the unique basis containing $S$. The forcing number $f_\{G\}(W, \dim )$ of $W$ in $G$ is the minimum cardinality of a forcing subset for $W$, while the forcing dimension $f(G, \dim )$ of $G$ is the smallest forcing number among all bases of $G$. The forcing dimensions of some well-known graphs are determined. It is shown that for all integers $a, b$ with $0 \le a \le b$ and $b \ge 1$, there exists a nontrivial connected graph $G$ with $f(G) = a$ and $\dim (G) = b$ if and only if $\lbrace a, b\rbrace \ne \lbrace 0, 1\rbrace $.},

author = {Chartrand, Gary, Zhang, Ping},

journal = {Mathematica Bohemica},

keywords = {resolving set; basis; dimension; forcing dimension; resolving set; basis; dimension; forcing dimension},

language = {eng},

number = {4},

pages = {711-720},

publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},

title = {The forcing dimension of a graph},

url = {http://eudml.org/doc/248877},

volume = {126},

year = {2001},

}

TY - JOUR

AU - Chartrand, Gary

AU - Zhang, Ping

TI - The forcing dimension of a graph

JO - Mathematica Bohemica

PY - 2001

PB - Institute of Mathematics, Academy of Sciences of the Czech Republic

VL - 126

IS - 4

SP - 711

EP - 720

AB - For an ordered set $W=\lbrace w_1, w_2, \cdots , w_k\rbrace $ 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),\cdots , 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. A resolving set of minimum cardinality is a basis for $G$ and the number of vertices in a basis is its (metric) dimension $\dim (G)$. For a basis $W$ of $G$, a subset $S$ of $W$ is called a forcing subset of $W$ if $W$ is the unique basis containing $S$. The forcing number $f_{G}(W, \dim )$ of $W$ in $G$ is the minimum cardinality of a forcing subset for $W$, while the forcing dimension $f(G, \dim )$ of $G$ is the smallest forcing number among all bases of $G$. The forcing dimensions of some well-known graphs are determined. It is shown that for all integers $a, b$ with $0 \le a \le b$ and $b \ge 1$, there exists a nontrivial connected graph $G$ with $f(G) = a$ and $\dim (G) = b$ if and only if $\lbrace a, b\rbrace \ne \lbrace 0, 1\rbrace $.

LA - eng

KW - resolving set; basis; dimension; forcing dimension; resolving set; basis; dimension; forcing dimension

UR - http://eudml.org/doc/248877

ER -

## References

top- On $k$-dimensional graphs and their bases. Submitted, .
- Resolvability in graphs and the metric dimension of a graph, (to appear). (to appear)
- On the geodetic number of a graph, (to appear). (to appear) MR1871701
- Resolvability and the upper dimension of graphs, (to appear). (to appear) MR1763834
- The directed distance dimension of oriented graphs, Math. Bohem. 125 (2000), 155–168. (2000) MR1768804
- On the dimension of oriented graphs, (to appear). (to appear) MR1863436
- The geodetic number of an oriented graph, European J. Combin. 21 (2000), 181–189. (2000) MR1742433
- The forcing geodetic number of a graph, Discuss. Math. Graph Theory 19 (1999), 45–58. (1999) MR1704390
- The chromatic forcing number of a graph, (to appear). (to appear)
- A survey of forcing parameters in graph theory. Preprint, .
- On the metric dimension of a graph, Ars Combin. 2 (1976), 191–195. (1976) MR0457289
- The graph reconstruction number, J. Graph Theory 9 (1985), 451–454. (1985) MR0890233
- The dimension of unicyclic graphs. Submitted, (to appear). (to appear)
- Leaves of trees, Congress. Numer. 14 (1975), 549–559. (1975) Zbl0316.05102MR0422062
- Dominating and reference sets in graphs, J. Math. Phys. Sci. 22 (1988), 445–455. (1988) MR0966610

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.