๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Randomly planar graphs

โœ Scribed by Daniel C. Isaksen; David P. Moulton

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
189 KB
Volume
175
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

โœฆ Synopsis

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 eulerian [2], randomly traceable [1], randomly matchable , and randomly decomposable [3] graphs. We continue in this vein by randomizing planarity. Throughout this note, G will denote a finite connected graph with labelled vertices. For the sake of brevity, we will only provide sketches of proofs.

๐Ÿ“œ SIMILAR VOLUMES

Randomly matchable graphs
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
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

On randomly -dimensional graphs
On randomly -dimensional graphs
โœ Mohsen Jannesari; Behnaz Omoomi ๐Ÿ“‚ Article ๐Ÿ“… 2011 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 254 KB

## 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 disti

On randomly Hamiltonian graphs
On randomly Hamiltonian graphs
โœ Carsten Thomassen ๐Ÿ“‚ Article ๐Ÿ“… 1973 ๐Ÿ› Springer ๐ŸŒ English โš– 801 KB