✦ LIBER ✦

Recognizing locally equivalent graphs

✍ Scribed by André Bouchet

Publisher: Elsevier Science
Year: 1993
Tongue: English
Weight: 771 KB
Volume: 114
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(93)90357-y

No coin nor oath required. For personal study only.

✦ Synopsis

Bouchet, A., Recognizing locally equivalent graphs, Discrete Mathematics 114 (1993) 75-86.

To locally complement a simple graph Fat one of its vertices u is to replace the subgraph induced by F on n(o)= {w: w is an edge of F} by the complementary subgraph. Graphs related by a sequence of local complementations are said to be locally equivalent. We describe invariants of locally equivalent graphs and a polynomial algorithm to recognize locally equivalent graphs. An application is given to counting the number of graphs locally equivalent to a given one.

📜 SIMILAR VOLUMES

Recognizing decomposable graphs

✍ V. Chvátal 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 129 KB

## Abstract A graph is called decomposable if its vertices can be colored red and blue in such a way that each color appears on at least one vertex but each vertex v has at most one neighbor having a different color from v. We point out a simple and efficient algorithm for recognizing decomposable

Locally C∗-equivalent algebras

✍ Joachim Cuntz 📂 Article 📅 1976 🏛 Elsevier Science 🌐 English ⚖ 712 KB

Locally Pancyclic Graphs

✍ Ladislav Stacho 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 215 KB

We prove the following theorem. Let G be a graph of order n and let W V(G). If |W | 3 and d G (x)+d G ( y) n for every pair of non-adjacent vertices x, y # W, then either G contains cycles C 3 ,

Locally petersen graphs

✍ J. I. Hall 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 684 KB

## Abstract A graph Γ is locally Petersen if, for each point __t__ of Γ, the graph induced by Γ on all points adjacent to __t__ is isomorphic to the Petersen graph. We prove that there are exactly three isomorphism classes of connected, locally Petersen graphs and further characterize these graphs

N2-locally disconnected graphs

✍ Zdenĕk Ryjác̆ek 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 269 KB

The edge-induced subgraph on the set of all edges of a graph G that are adjacent to a given vertex x is called the neighbourhood of the second type of x in G and is denoted by N2(x, G) (an edge yz is said to be adjacent to x if y # x fz and y or z is adjacent to x). A graph G is NJocally disconnecte

On ?-equivalence and ?-equivalence of gr

On ?-equivalence and ?-equivalence of graphs

✍ Du, Qingyan 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 336 KB 👁 1 views

W e define a partial ordering on the set of a-polynomials as well as a vertex splitting operation on the set of graphs, and introduce the notions of (r-equivalence and (r- uniqueness of graphs. Let a ( G ) be the a-polynomial of a graph G and a ( G ) = (r(GC). Let H = (G, u , A, 5) be a vertex spli