✦ LIBER ✦

Distinguishing geometric graphs

✍ Scribed by Michael O. Albertson; Debra L. Boutin

Publisher: John Wiley and Sons
Year: 2006
Tongue: English
Weight: 196 KB
Volume: 53
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20171

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We begin the study of distinguishing geometric graphs. Let G be a geometric graph. An automorphism of the underlying graph that preserves both crossings and noncrossings is called a geometric automorphism. A labeling, f: V(G) → {1, 2, … , r}, is said to be r‐distinguishing if no nontrivial geometric automorphism preserves the labels. The distinguishing number of G is the minimum r such that G has an r‐distinguishing labeling. We show that when K~n~ is not the nonconvex K~4~, it can be 3‐distinguished. Furthermore, when n ≥ 6, there is a K~n~ that can be 1‐distinguished. For n ≥ 4, K~2,n~ can realize any distinguishing number between 1 and n inclusive. Finally, we show that every K~3,3~ can be 2‐distinguished. We also offer several open questions. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 135–150, 2006

📜 SIMILAR VOLUMES

Distinguishing Cartesian powers of graph

Distinguishing Cartesian powers of graphs

✍ Wilfried Imrich; Sandi Klavžar 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 132 KB

The distinguishing number D(G) of a graph is the least integer d such that there is a d-labeling of the vertices of G that is not preserved by any nontrivial automorphism of G. We show that the distinguishing number of the square and higher powers of a connected graph G = K 2 , K 3 with respect to t

Geometric graph homomorphisms

✍ Debra L. Boutin; Sally Cockburn 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 159 KB

## Abstract A __geometric graph__ is a simple graph drawn on points in the plane, in general position, with straightline edges. A __geometric__ __homomorphism__ from to is a vertex map that preserves adjacencies and crossings. This work proves some basic properties of geometric homomorphisms and

Note on Geometric Graphs

✍ Géza Tóth 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 206 KB

A geometric graph is a graph drawn in the plane so that the vertices are represented by points in general position and the edges are represented by straight line segments connecting the corresponding points. We show that a geometric graph of n vertices with no k+1 pairwise disjoint edges has at most

Vertex-distinguishing edge colorings of

Vertex-distinguishing edge colorings of graphs

✍ P. N. Balister; O. M. Riordan; R. H. Schelp 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 136 KB 👁 1 views

Certain graph invariants do not distingu

Certain graph invariants do not distinguish all graphs

✍ D. A. Chalcraft 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 193 KB

## Abstract This paper considers a certain fairly large class of graph invariants and shows that for any invariant in this class, there is a pair of nonisomorphic graphs that have the same invariant. Some explicit examples of such invariants are discussed.

Distinguished vertices in probabilistic

Distinguished vertices in probabilistic rooted graphs

✍ Gary Gordon; Ekaterina Jager 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 129 KB