Name
Abstract | ||
|---|---|---|
For a vertex v of a connected graph G and a subset S of V(G), the distance between v and S is d(v, S) = min{d(v, x) \x is an element of S}. For an ordered k-partition Pi = {S-1, S-2, ..., Sk(k)} of V(G), the code of v with respect to Pi is the k-vector c(Pi)(v) = (d(v, S-1), d(v, S-2), ...., d(v, S-k)). The k-partition Pi is a resolving partition if the k-vectors c(Pi)(v), v is an element of V(G), are distinct. The minimum k for which there is a resolving k-partition of V(G) is the partition dimension pd(G) of G. A resolving partition Pi = {S-1, S-2, ..., S-k} of V(G) is a resolving-coloring if each S-i (1 less than or equal to i less than or equal to k) is independent and the resolving-chromatic number chi(r)(G) is the minimum number of colors in a resolving-coloring of G. A resolving partition Pi = {S-1, S-2, ..., S-k} is acyclic if each subgraph <S-i> induced by S-i (1 less than or equal to i less than or equal to k) is acyclic in G. The minimum k for which there is a resolving acyclic k-partition of V(G) is the resolving acyclic number a(r)(G) of G. Thus 2 less than or equal to pd(G) less than or equal to a(r)(G) less than or equal to chi(r)(G) less than or equal to n for every connected graph G of order n greater than or equal to 2. We present bounds for the resolving acyclic number of a connected graph in terms of its arboricity, partition dimension, resolving-chromatic number, diameter, girth, and other parameters. Connected graphs of order n greater than or equal to 3 having resolving acyclic number 2, n, or n - 1 are characterized. |
Year | Venue | Keywords |
|---|---|---|
2004 | ARS COMBINATORIA | distance, resolving partition, acyclic resolving partition |
Field | DocType | Volume |
Graph,Discrete mathematics,Combinatorics,Mathematics | Journal | 70 |
ISSN | Citations | PageRank |
0381-7032 | 1 | 0.52 |
References | Authors | |
0 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Varaporn Saenpholphat | 1 | 30 | 5.60 |
| Ping Zhang | 2 | 292 | 47.70 |