✦ LIBER ✦

Locally 4-by-4 grid graphs

✍ Scribed by A. Blokhuis; A. E. Brouwer

Publisher: John Wiley and Sons
Year: 1989
Tongue: English
Weight: 680 KB
Volume: 13
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190130209

No coin nor oath required. For personal study only.

✦ Synopsis

We investigate locally grid graphs. The main results are (i) a characterization of the Johnson graphs (and certain quotients of these) as locally grid graphs such that two points at distance 2 have precisely four common neighbors, and (ii) a complete determination of all graphs that are locally a 4 x 4 grid (it turns out that there are four such graphs, with 35, 40, 40, and 70 vertices).

📜 SIMILAR VOLUMES

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

4-valent graphs

✍ T. C. Enns 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 707 KB

Let bk}k22, k+4 be a sequence of non-negative integers which satisfies 8 + &(k -4)pk = 0. Then there exists an integer p4 such that there exists a 2-connected planar graph with exactly pk k-gons as faces for all k 1 2 . This paper determines all such p4 when pk = 0 f o r k 1 5 and determines that th

Recognizing locally equivalent graphs

✍ André Bouchet 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 771 KB

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 comp

4-chromatic projective graphs

✍ Youngs, D. A. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 464 KB

We construct a family of 4-chromatic graphs which embed on the projective plane, and characterize the edge-critical members. The family includes many well known graphs, and also a new sequence of graphs, which serve to improve Gallai's bound on the length of the shortest odd circuit in a 4-chromatic

Uncontractable 4-connected graphs

✍ Nicola Martinov 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 98 KB

## Abstract The only uncontractable 4‐connected graphs are __C__^2^~__n__~ for __n__ ≥ 5 and the line graphs of the cubic cyclically 4‐connected graphs.