𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Representations of graphs modulo n

✍ Scribed by Anthony B. Evans; Gerd H. Fricke; Carl C. Maneri; Terry A. McKee; Manley Perkel

Publisher
John Wiley and Sons
Year
1994
Tongue
English
Weight
757 KB
Volume
18
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A graph is representable modulo n if its vertices can be labeled with distinct integers between 0 and n, the difference of the labels of two vertices being relatively prime to n if and only if the vertices are adjacent. ErdΕ‘s and Evans recently proved that every graph is representable modulo some positive integer. We derive a combinatorial formulation of representability modulo n and use it to characterize those graphs representable modulo certain types of integers, in particular integers with only two prime divisors. Other facets of representability are also explored. We obtain information about the values of n modulo which paths and cycles are representable.

πŸ“œ SIMILAR VOLUMES

Cycles of length 0 modulo 4 in graphs
Cycles of length 0 modulo 4 in graphs
✍ Nathaniel Dean; Linda Lesniak; Akira Saito πŸ“‚ Article πŸ“… 1993 πŸ› Elsevier Science 🌐 English βš– 829 KB

In several papers a variety of questions have been raised concerning the existence of cycles of length Omod k in graphs. For the case k=4, we answer three of these questions by showing that a graph G contains such a cycle provided it has any of the following three properties: (1) G has minimum degre

Cycles of length 2 modulo 3 in graphs
Cycles of length 2 modulo 3 in graphs
✍ Akira Saito πŸ“‚ Article πŸ“… 1992 πŸ› Elsevier Science 🌐 English βš– 274 KB

Saito, A., Cycles of length 2 modulo 3 in graphs, Discrete Mathematics 101 (1992) 285-289. We prove that if a graph G of minimum degree at least 3 has no cycle of length 2 (mod 3), then G has an induced subgraph which is isomorphic to either K4 or Ks,s. The above result together with its relatively