✦ LIBER ✦

On randomly -dimensional graphs

✍ Scribed by Mohsen Jannesari; Behnaz Omoomi

Publisher: Elsevier Science
Year: 2011
Tongue: English
Weight: 254 KB
Volume: 24
Category: Article
ISSN: 0893-9659
DOI: 10.1016/j.aml.2011.03.024

No coin nor oath required. For personal study only.

✦ Synopsis

a b s t r a c t

For an ordered set W = {w 1 , w 2 , . . . , w k } of vertices and a vertex v in a connected graph G, the ordered k-vector r(v|W

representation of v with respect to W , where d(x, y) is the distance between the vertices x and y. The set W is called a resolving set for G if distinct vertices of G have distinct representations with respect to W . A resolving set for G with minimum cardinality is called a basis of G and its cardinality is the metric dimension of G. A connected graph G is called a randomly k-dimensional graph if each k-set of vertices of G is a basis of G. In this work, we study randomly k-dimensional graphs and provide some properties of these graphs.

📜 SIMILAR VOLUMES

On randomly Hamiltonian graphs

✍ Carsten Thomassen 📂 Article 📅 1973 🏛 Springer 🌐 English ⚖ 801 KB

Randomly matchable graphs

✍ David P. Summer 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 190 KB

## Abstract A graph is defined to be randomly matchable if every matching of __G__ can be extended to a perfect matching. It is shown that the connected randomly matchable graphs are precisely __K__~2__n__~ and __K~n,n~__ (__n__ ≥ 1).

Randomly decomposable graphs

✍ Sergio Ruiz 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 362 KB

A nonempty graph G is randomly H-decomposable if every family of edge-disjoint subgraphs of G, each subgraph isomorphic to H, can be extended to an H-decomposition of G. A characterization of those randomly H-decomposable graphs is given whenever H has two edges. Some related questions are discussed

Randomly planar graphs

✍ Daniel C. Isaksen; David P. Moulton 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 189 KB

A graph G is randomly planar if every planar embedding of every connected subgraph of G can be extended to a planar embedding of G. We classify these graphs. ## 1. Introduction Many properties of graphs have been 'randomized' by various mathematicians. Examples include the notions of randomly eule

On graphs with randomly deleted edges

✍ A. K. Kelmans 📂 Article 📅 1981 🏛 Akadmiai Kiad 🌐 English ⚖ 560 KB

On Markov Chains for Randomly H-Coloring

On Markov Chains for Randomly H-Coloring a Graph

✍ Colin Cooper; Martin Dyer; Alan Frieze 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 144 KB

Let H = W F be a graph without multiple edges, but with the possibility of having loops. Let G = V E be a simple graph. A homomorphism c is a map c V → W with the property that v w ∈ E implies that c v c w ∈ F. We will often refer to c v as the color of v and c as an H-coloring of G. We consider the